Binary Tree Depth
出处
Compute the depth of a binary tree.
Solution
回顾树的高度定义:从根节点到某个节点的路径长度称为该节点的层数(level),根节点为第0层,非根节点的层数是其父节点的层数加1。树的高度定义为该树中层数最大的叶节点的层数加1。判断树的高度符合D&C的 条件:对于某个节点,其高度为左子树和右子树高度的较大者加1,即原问题依赖于两个子问题。对于递归的实现,出口为传入节点为空,此时应该返回高度0。
Complexity
该算法遍历树的所有节点,故复杂度O(n)。
Code
int depthBT(Node root){
if (root == null) return 0;
return Math.max(depthBT(root.left), depthBT(root.right))+1;
}