【DFS, 哈希表】找树左下角的值

题目

513. 找树左下角的值

---

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

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

示例 1:

输入: root = [2,1,3]
输出: 1

示例 2:

输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7

提示:

• 二叉树的节点个数的范围是 [1,10^4]
• -2^31 <= Node.val <= 2^31 - 1

解题

方法一：DFS

思路

深度优先搜索找出二叉树中每一层最左边的节点，然后取出最下面那一层的最左节点的值返回。

应为节点的范围是 $[1, 10^4]$ ，故二叉树最差情况下退化成链表也只有 1000 层，创建一个大于该值的数组(nodes)用来存放每一层中最左边的节点。

传入根节点与其层数0开始深搜，节点为空是递归结束条件，对于每个节点直接把该节点存入数组中第 depth 个中，然后递归地搜索右子节点和左子节点(因为需要取的是最左节点，所以先搜右节点再搜左节点，这样的话如果能保证最后在数组中该层存储的一定是最左的节点)。

代码

class Solution {
    private TreeNode[] nodes = new TreeNode[1010];

    public int findBottomLeftValue(TreeNode root) {
        dfs(root, 0);
        for (int i = nodes.length - 1; i >= 0; i--) {
            if (nodes[i] != null) return nodes[i].val;
        }
        return 0;
    }

    private void dfs(TreeNode node, int depth) {
        if (node == null) return;
        nodes[depth] = node;
        dfs(node.right, depth + 1);
        dfs(node.left, depth + 1);
    }
}

优化

维护一个最大层数(max)以及该层最左节点的值(ans)，在每次递归中，只有当前节点所在高度严格大于 max 时更新 max 以及把 ans 置为该节点的值，此时就应该先搜索左节点再搜右节点，因为这次每层只会更新一次，一定要保证某层第一次拿到的节点一定是该层的最左节点。

class Solution {
    private int max, ans;

    public int findBottomLeftValue(TreeNode root) {
        dfs(root, 1);
        return ans;
    }

    private void dfs(TreeNode node, int depth) {
        if (node == null) return;
        if (depth > max) {
            ans = node.val;
            max = depth;
        }
        dfs(node.left, depth + 1);
        dfs(node.right, depth + 1);
    }
}