Leetcode-104-二叉树的最大深度

Leecode-104-Maximum Depth of Binary Tree

思路：递归

题目描述：找出二叉树的最大深度

    1
   / \
  2   3
 / \     
4   5

• 返回深度：3（3层的二叉树）

Solution：递归

具体过程可以看下图：

1. 对于根节点：先找取左子树和右子树

2. 对于左子树2：继续向下找左子树

3. 找到左子树3

4. 左子树遍历完，找右子树

5. 再查找右子树的左子树5

6. 再查找右子树的右子树

7. 返回根节点左子树的最大深度

8. 最后遍历根节点的右子树

Java

Solution :

// 递归解法
class Solution{
    public int maxDepth(TreeNode root){
        if (root == null){
            return 0;
        }else {
            int left_height  = maxDepth(root.left);
            int right_height = maxDepth(root.right);
            return Math.max(left_height,right_height) + 1;
        }
    }
}

• 时间复杂度：O(N) N是节点的个数（每个节点访问一次）
• 空间复杂度：
  • 在最糟糕的情况下，就如上图的例子而言，树是完全不平衡的（例如每个节点只剩下左子节点，递归将会被调用N次，也就是树的高度）。因此保持调用栈的存储将是O(N)
  • 但在最好的情况下（树是完全平衡的），树的高度将是O(logn)。因此，在这种情况下的空间复杂度是O(logn)

方法二： BFS

• 树的层序遍历 / 广度优先搜索往往利用 队列 实现。
• 关键点： 每遍历一层，则计数器 +1+1 ，直到遍历完成，则可得到树的深度。

思路：

• 特例处理： 当 root 为空，直接返回 深度 0 。
• 初始化： 队列 queue （加入根节点 root ），计数器 res = 0。

• 循环遍历：
  1. 初始化一个空列表 tmp , 用于存储下一层节点
  2. 遍历队列：遍历queue 的 各节点node ，并将其左右子节点加入tmp
  3. 更新queue 执行 queue = tmp 将下一层节点复制给queue
  4. 统计层数 执行 res += 1

• 返回值： 返回 res 即可。

// BFS(层序遍历)
// 树的层序遍历 / 广度优先搜索往往利用 队列 实现。
class Solution{
    public int maxDepth(TreeNode root){
        if (root == null){
            return 0;
        }

        LinkedList<TreeNode> queue = new LinkedList<>();
        LinkedList<TreeNode> tmp =   queue;
        queue.add(root);
        int res = 0;

        while(!queue.isEmpty()) {
            tmp = new LinkedList<>();
            for(TreeNode node : queue) {
                if(node.left != null) tmp.add(node.left);
                if(node.right != null) tmp.add(node.right);
            }
            queue = tmp;
            res++;
        }
        return res;
    }
}

复杂度分析：

• 时间复杂度 O(N) ： NN 为树的节点数量，计算树的深度需要遍历所有节点。
• 空间复杂度 O(N) ： 最差情况下（当树平衡时），队列 queue 同时存储 N/2 个节点。

打赏