力扣 - 剑指 Offer 55 - I. 二叉树的深度

题目

剑指 Offer 55 - I. 二叉树的深度

思路1(DFS)

  • 后续遍历吧,先遍历到最深(递归到末尾返回0),然后从后面一步一步比较取大的值返回,每次返回层数都加1,
  • 执行流程是怎样的:比如其中一个节点左子树为空,右子树有一个叶子节点,那么 0 > 1 ,肯定选 1 ,再加上当前一层 1 ,返回 2 给父节点;然后到了父节点对两个子节点的比较,其中一个节点就是刚才的 2 ,如果另一个返回的深度为4,那么就取 4 ,再加上当前的 1 返回 5 给它的父节点……直到返回到根节点,此时就得到了二叉树的最大深度

代码

class Solution {
    public int maxDepth(TreeNode root) {
        return dfs(root);
    }

    public int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }

        // 获取左子树和右子树的深度
        int l = dfs(root.left);
        int r = dfs(root.right);

        // 取其中较大的一个深度,并且加上当前一层 1 传递给父节点
        return Math.max(l, r) + 1;
    }
}

复杂度分析

  • 时间复杂度:\(O(N)\)
  • 空间复杂度:\(O(N)\)

思路2(BFS)

  • BFS/广度优先遍历,即层序遍历,这种可能会更好理解一点,这种解法思路就是每次遍历一层,层数res就加 1,直到遍历到最后一层,此时res就是二叉树的最大深度了
  • 使用队列存储节点,每次循环先计算队列中有几个节点(就是每层的节点个数),然后将这些节点一次性出队,同时还要判断出队的节点是否有子节点,如果有就入队,这就算完成了一层的遍历……直到遍历到最后一层

代码

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int res = 0;
        Queue queue = new LinkedList<>();
        queue.offer(root);

        // 层序遍历/广度优先遍历/BFS
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                size--;
            }
            // 每遍历一层,层数加 1
            res++;
        }

        return res;
    }
}

复杂度分析

  • 时间复杂度:\(O(N)\)
  • 空间复杂度:\(O(N)\),最差情况下(当树平衡时),队列 queue 同时存储 \(N/2\) 个节点。

你可能感兴趣的