题解 | #二叉树的深度#

38、二叉树的深度

解题思路：

题目是 从根节点到叶节点的路径，所以就是求出二叉树的层数即可。

方法一：层次遍历

我们先来回顾一下二叉树的层次遍历，一般我们都是用队列去实现的。

步骤：

1、先创建一个队列，将根节点入队；

2、队列不为空，进入循环：

• 出队一个节点
• 将当前节点的左右节点入队（不为空时）
• 此时当前层的所有节点的左右子节点都入队

4、最后当队列中无节点的时候，此时已全部遍历完全部节点。

有了上面的步骤，我们只需要在每一层的所有节点的左右子节点都入完队的时候，就计数，最后则可以得到结果。

代码：

public int TreeDepth(TreeNode root) {
        if(root == null)
            return 0;
        Queue<TreeNode> q = new LinkedList<>();
        // 根节点入队
        q.add(root);
        // 记录深度
        int high = 0;
        // 当队列不为空的时候
        while(!q.isEmpty()){
            // 当前层的节点数
            int size = q.size();
            // 将当前层的节点的左右子节点都入队
            while(size != 0){
                // 出队
                TreeNode node = q.poll();
                // 有左节点的时候
                if(node.left != null)
                    q.add(node.left);
                // 有右节点的时候
                if(node.right != null)
                    q.add(node.right);
                // 出一个
                size--;
            }
            // 里层循环结束则证明一走完一层，所以深度加1
            high++;
        }
        return high;
    }

复杂度分析：

时间复杂度：O(n)。 节点的个数。

空间复杂度：O(n)。队列占用的空间。

方法二：深度遍历

我们知道二叉树的深度，肯定是等于其左子树与右子树的深度的最大值再+1。（加1就是加上当前层）

深度遍历可以采用栈或者递归实现，本文采用递归的做法实现，代码很简单易懂。

当递归到节点为null的时候，则为终止条件，此时会返回0。

接着会取左右子树中最大值+1。

例子：

假设父节点F，左节点为L，L的左右节点都为null。

则此时父节点F的左子树的深度则为1。

代码：

public int TreeDepth(TreeNode root) {
        if(root == null)
            return 0;
        int l = TreeDepth(root.left);
        int r = TreeDepth(root.right);
        return Math.max(l,r)+1;
    }

复杂度分析：

时间复杂度：O(n)。 遍历的节点的个数。

空间复杂度：O(n)。退化成链表的时候，则递归深度为n。