LC 513. 找树左下角的值

题目描述

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

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

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

示例 1:

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

输出: 1

示例 2:

1
2
3
输入: [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 存储的是最后一层最靠左的节点。

Java 代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;
}
}

C++ 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
deque<TreeNode*> d;
d.push_back(root);
int ans = 0;
while (!d.empty()) {
int sz = d.size();
ans = d.front()->val;
while (sz-- > 0) {
TreeNode* poll = d.front();
d.pop_front();
if (poll->left != nullptr) d.push_back(poll->left);
if (poll->right != nullptr) d.push_back(poll->right);
}
}
return ans;
}
};

Python 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
d = deque([root])
ans = 0
while d:
sz = len(d)
ans = d[0].val
while sz > 0:
poll = d.popleft()
if poll.left:
d.append(poll.left)
if poll.right:
d.append(poll.right)
sz -= 1
return ans

TypeScript 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
function findBottomLeftValue(root: TreeNode | null): number {
const d = [root];
let ans = 0;
while (d.length > 0) {
const sz = d.length;
ans = d[0].val;
for (let i = 0; i < sz; i++) {
const poll = d.shift()!;
if (poll.left) d.push(poll.left);
if (poll.right) d.push(poll.right);
}
}
return ans;
};

  • 时间复杂度:$O(n)$
  • 空间复杂度:最坏情况下所有节点都在同一层,复杂度为 $O(n)$

DFS

同理,可以使用 DFS 进行树的遍历,每次优先 DFS 当前节点的左子树,每次第一次搜索到当前深度 depth 时,必然是当前深度的最左节点,此时用当前节点值来更新 ans

Java 代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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);
}
}

C++ 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int maxv = 0, ans = 0;
int findBottomLeftValue(TreeNode* root) {
dfs(root, 1);
return ans;
}
void dfs(TreeNode* root, int depth) {
if (!root) return;
if (depth > maxv) {
maxv = depth; ans = root->val;
}
dfs(root->left, depth + 1);
dfs(root->right, depth + 1);
}
};

Python 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
self.maxv, self.ans = 0, 0
self.dfs(root, 1)
return self.ans

def dfs(self, root: TreeNode, depth: int) -> None:
if not root:
return
if depth > self.maxv:
self.maxv = depth
self.ans = root.val
self.dfs(root.left, depth + 1)
self.dfs(root.right, depth + 1)

TypeScript 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
let max, ans;
function dfs(root: TreeNode | null, depth: number): void {
if (!root) return;
if (depth > max) {
max = depth;
ans = root.val;
}
dfs(root.left, depth + 1);
dfs(root.right, depth + 1);
}
function findBottomLeftValue(root: TreeNode | null): number {
max = 0; ans = 0;
dfs(root, 1);
return ans;
};

  • 时间复杂度:$O(n)$
  • 空间复杂度:最坏情况下退化成链,递归深度为 $n$。复杂度为 $O(n)$

最后

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

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

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!