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;
}