题目形容
这是 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 多平台公布