LeetCode 513. 找树左下角的值 DFS、BFS题解，熟悉树形问题的DFS、BFS常用解法。

题目

513. 找树左下角的值

https://leetcode.cn/problems/find-bottom-left-tree-value/

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

DFS

思路

我们用DFS的思路来一杆子戳到底，遍历整棵树。

关键点：

  • 用maxDepth来实时维护树的深度，在深度更深的情况下更新最下层的值；
  • 先递归进入右子树，再递归进入左子树：
    • 左右子树深度不一致时，由深度决定处理的是最深的节点；
    • 左右子树深度一致时，后进入左子，保证最后处理的是最深最左的节点；

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

static class DFS {
    /*
        * 执行用时：
        * 0 ms
        * , 在所有 Java 提交中击败了
        * 100.00%
        * 的用户
        * 内存消耗：
        * 41.4 MB
        * , 在所有 Java 提交中击败了
        * 11.01%
        * 的用户
        * 通过测试用例：
        * 76 / 76
        */

    int maxDepth;

    int val;

    public int findBottomLeftValue(TreeNode root) {
        val = 0;
        maxDepth = 0;
        dfs(root, 0);
        return val;
    }

    private void dfs(TreeNode node, int depth) {
        if (node == null) {
            return;
        }
        depth++;
        if (maxDepth < depth) {
            maxDepth = depth;
        }
        if (depth == maxDepth) {
            val = node.val;
        }
        dfs(node.right, depth);
        dfs(node.left, depth);
    }
}

复杂度分析

时间

整体遍历一次树，时间复杂度取决于树节点数，复杂度O(n)，n表示树节点数。

空间

递归开辟树深度的栈空间，最差退化成链表，空间复杂度O(n)。

BFS

思路

用BFS的思路来逐层遍历整棵树。

关键点：

  • 队列中最后处理的一定是最深的层；
  • 先入队右子，后入队左子，保证最后处理的一定是最左节点；

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

static class BFS {

    /*
        * 执行用时：
        * 1 ms
        * , 在所有 Java 提交中击败了
        * 63.04%
        * 的用户
        * 内存消耗：
        * 40.8 MB
        * , 在所有 Java 提交中击败了
        * 82.06%
        * 的用户
        * 通过测试用例：
        * 76 / 76
        */

    /**
        * BFS，入队时左子节点后入队，保证最后处理的是最后一层的最左值
        */
    public int findBottomLeftValue(TreeNode root) {
        int ans = 0;
        Queue<TreeNode> q = new ArrayDeque<>();
        if (root != null) {
            q.offer(root);
        }
        while (!q.isEmpty()) {
            for (int size = q.size(); size > 0; size--) {
                TreeNode node = q.poll();
                ans = node.val;
                if (node.right != null) {
                    q.offer(node.right);
                }
                if (node.left != null) {
                    q.offer(node.left);
                }
            }
        }
        return ans;
    }
}

复杂度分析

时间

每个节点入队一次，出队一次，时间复杂度O(n)，n表示树节点数。

空间

额外使用了一个队列维护层序信息，队列最多时持有最后一层（或者是倒数第二层中间）最多元素，空间复杂度近似不到O(n)。