题目形容

这是 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

应用 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 进行树的遍历，每次优先 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);    }}
  • 工夫复杂度：$O(n)$
  • 空间复杂度：最坏状况下进化成链，递归深度为 $n$。复杂度为 $O(n)$

最初

这是咱们「刷穿 LeetCode」系列文章的第 No.513 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。

在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou... 。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

本文由mdnice多平台公布