侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-06-22 / 0 评论 / 0 点赞 / 40 阅读 / 570 字 / 正在检测是否收录...

题目

513. 找树左下角的值


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

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

示例 1:

image-20220622230017378

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

示例 2:

image-20220622230045953

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

提示:

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

解题

方法一:DFS

思路

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

应为节点的范围是 [1,104][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);
    }
}
0

评论区