关于程序员:高频笔试题513-找树左下角的值

1次阅读

共计 1284 个字符，预计需要花费 4 分钟才能阅读完成。

这是 LeetCode 上的 513. 找树左下角的值 ，难度为中等。

Tag :「BFS」、「DFS」、「树的遍历」

给定一个二叉树的根节点 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$

应用 BFS 进行「层序遍历」，每次用以后层的首个节点来更新 ans，当 BFS 完结后，ans 存储的是最初一层最靠左的节点。

代码：

class Solution {public int findBottomLeftValue(TreeNode root) {Deque<TreeNode> d = new ArrayDeque<>();
        d.addLast(root);
        int ans = 0;
        while (!d.isEmpty()) {int sz = d.size();
            ans = d.peek().val;
            while (sz-- > 0) {TreeNode poll = d.pollFirst();
                if (poll.left != null) d.addLast(poll.left);
                if (poll.right != null) d.addLast(poll.right);
            }
        }
        return ans;
    }
}

工夫复杂度：$O(n)$
空间复杂度：最坏状况下所有节点都在同一层，复杂度为 $O(n)$

同理，能够应用 DFS 进行树的遍历，每次优先 DFS 以后节点的左子树，每次第一次搜寻到以后深度 depth 时，必然是以后深度的最左节点，此时用以后节点值来更新 ans。

代码：

class Solution {
    int max, ans;
    public int findBottomLeftValue(TreeNode root) {dfs(root, 1);
        return ans;
    }
    void dfs(TreeNode root, int depth) {if (root == null) return ;
        if (depth > max) {max = depth; ans = root.val;}
        dfs(root.left, depth + 1);
        dfs(root.right, depth + 1);
    }
}