LeetCode513-找树左下角的值

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/find-bottom-left-tree-value/

中文链接：https://leetcode-cn.com/problems/find-bottom-left-tree-value/

题目详述

给定一个二叉树，在树的最后一行找到最左边的值。

示例 1:

1
2
3
4
5
6
7
8
输入:

    2
   / \
  1   3

输出:
1

示例 2:

1
2
3
4
5
6
7
8
9
10
11
12
输入:

        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7

输出:
7

注意: 您可以假设树（即给定的根节点）不为 NULL。

题目详解

方法一：运用 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
public class LeetCode_00513 {

    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        int res = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                TreeNode node = queue.poll();
                if (i == 0) {
                    res = node.val;
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return res;
    }
}

方法二：运用 DFS。

  • 构造搜索方法 dfs，当前树的最后一行的最左边结点的值和层数。
  • 如果当前结点为叶子节点，直接返回当前结点值的和层数。
  • 如果当前结点的左子树为空，右子树不为空，返回右子树递归搜索的结果。
  • 如果当前结点的左子树不为空，右子树为空，返回左子树递归搜索的结果。
  • 如果当前结点的左子树和右子树均不为空。则进行递归得到左子树的右子树搜索得到的结果，记为 left 和 right。
  • 如果 left[1] <= right[1]，即 left 比 right 层数更深或者层数相同（层数相同找左边即 left），返回 left，否则返回 right。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class LeetCode_00513 {

    public int findBottomLeftValue(TreeNode root) {
        int[] res = dfs(root, 0);
        return res[0];
    }

    private int[] dfs(TreeNode root, int level) {
        if (root.left == null && root.right == null) return new int[]{root.val, level};
        if (root.left == null) return dfs(root.right, level + 1);
        if (root.right == null) return dfs(root.left, level + 1);
        int[] left = dfs(root.left, level + 1);
        int[] right = dfs(root.right, level + 1);
        return left[1] >= right[1] ? left : right;
    }
}