第五章 - 高频考题（中等）
1906. 查询差绝对值的最小值
0513. 找树左下角的值
题目地址（513. 找树左下角的值）
题目描述
1
给定一个二叉树，在树的最后一行找到最左边的值。
2
3
示例 1:
4
5
输入:
6
7
2
8
/ \
9
1 3
10
11
输出:
12
1
13
14
15
示例 2:
16
17
输入:
18
19
1
20
/ \
21
2 3
22
/ / \
23
4 5 6
24
/
25
7
26
27
输出:
28
7
Copied!
BFS
思路
其实问题本身就告诉你怎么做了
在树的最后一行找到最左边的值。
问题再分解一下
- 找到树的最后一行
- 找到那一行的第一个节点
不用层序遍历简直对不起这个问题，这里贴一下层序遍历的流程
1
令curLevel为第一层节点也就是root节点
2
定义nextLevel为下层节点
3
遍历node in curLevel,
4
nextLevel.push(node.left)
5
nextLevel.push(node.right)
6
令curLevel = nextLevel, 重复以上流程直到curLevel为空
Copied!
代码
- 代码支持：JS，Python，Java，CPP, Go, PHP
JS Code：
1
var findBottomLeftValue = function (root) {
2
let curLevel = [root];
3
let res = root.val;
4
while (curLevel.length) {
5
let nextLevel = [];
6
for (let i = 0; i < curLevel.length; i++) {
7
curLevel[i].left && nextLevel.push(curLevel[i].left);
8
curLevel[i].right && nextLevel.push(curLevel[i].right);
9
}
10
res = curLevel[0].val;
11
curLevel = nextLevel;
12
}
13
return res;
14
};
Copied!
Python Code:
1
class Solution(object):
2
def findBottomLeftValue(self, root):
3
queue = collections.deque()
4
queue.append(root)
5
while queue:
6
length = len(queue)
7
res = queue[0].val
8
for _ in range(length):
9
cur = queue.popleft()
10
if cur.left:
11
queue.append(cur.left)
12
if cur.right:
13
queue.append(cur.right)
14
return res
Copied!
Java：
1
class Solution {
2
Map<Integer,Integer> map = new HashMap<>();
3
int maxLevel = 0;
4
public int findBottomLeftValue(TreeNode root) {
5
if (root == null) return 0;
6
LinkedList<TreeNode> deque = new LinkedList<>();
7
deque.add(root);
8
int res = 0;
9
while(!deque.isEmpty()) {
10
int size = deque.size();
11
for (int i = 0; i < size; i++) {
12
TreeNode node = deque.pollFirst();
13
if (i == 0) {
14
res = node.val;
15
}
16
if (node.left != null)deque.addLast(node.left);
17
if (node.right != null)deque.addLast(node.right);
18
}
19
}
20
return res;
21
}
22
}
Copied!
CPP：
1
class Solution {
2
public:
3
int findBottomLeftValue_bfs(TreeNode* root) {
4
queue<TreeNode*> q;
5
TreeNode* ans = NULL;
6
q.push(root);
7
while (!q.empty()) {
8
ans = q.front();
9
int size = q.size();
10
while (size--) {
11
TreeNode* cur = q.front();
12
q.pop();
13
if (cur->left )
14
q.push(cur->left);
15
if (cur->right)
16
q.push(cur->right);
17
}
18
}
19
return ans->val;
20
}
21
}
Copied!
Go Code:
1
/**
2
* Definition for a binary tree node.
3
* type TreeNode struct {
4
* Val int
5
* Left *TreeNode
6
* Right *TreeNode
7
* }
8
*/
9
func findBottomLeftValue(root *TreeNode) int {
10
res := root.Val
11
curLevel := []*TreeNode{root} // 一层层遍历
12
for len(curLevel) > 0 {
13
res = curLevel[0].Val
14
var nextLevel []*TreeNode
15
for _, node := range curLevel {
16
if node.Left != nil {
17
nextLevel = append(nextLevel, node.Left)
18
}
19
if node.Right != nil {
20
nextLevel = append(nextLevel, node.Right)
21
}
22
}
23
curLevel = nextLevel
24
}
25
return res
26
}
Copied!
PHP Code:
1
/**
2
* Definition for a binary tree node.
3
* class TreeNode {
4
* public $val = null;
5
* public $left = null;
6
* public $right = null;
7
* function __construct($value) { $this->val = $value; }
8
* }
9
*/
10
class Solution
11
{
12
13
/**
14
* @param TreeNode $root
15
* @return Integer
16
*/
17
function findBottomLeftValue($root)
18
{
19
$curLevel = [$root];
20
$res = $root->val;
21
while (count($curLevel)) {
22
$nextLevel = [];
23
$res = $curLevel[0]->val;
24
foreach ($curLevel as $node) {
25
if ($node->left) $nextLevel[] = $node->left;
26
if ($node->right) $nextLevel[] = $node->right;
27
}
28
$curLevel = $nextLevel;
29
}
30
return $res;
31
}
32
}
Copied!
复杂度分析
- 时间复杂度：$O(N)$，其中 N 为树的节点数。
- 空间复杂度：$O(Q)$，其中 Q 为队列长度，最坏的情况是满二叉树，此时和 N 同阶，其中 N 为树的节点总数
DFS
思路
树的最后一行找到最左边的值，转化一下就是找第一个出现的深度最大的节点，这里用先序遍历去做，其实中序遍历也可以，只需要保证左节点在右节点前被处理即可。 具体算法为，先序遍历 root，维护一个最大深度的变量，记录每个节点的深度，如果当前节点深度比最大深度要大，则更新最大深度和结果项。
代码
代码支持：JS，Python，Java，CPP
JS Code：
1
function findBottomLeftValue(root) {
2
let maxDepth = 0;
3
let res = root.val;
4
5
dfs(root.left, 0);
6
dfs(root.right, 0);
7
8
return res;
9
10
function dfs(cur, depth) {
11
if (!cur) {
12
return;
13
}
14
const curDepth = depth + 1;
15
if (curDepth > maxDepth) {
16
maxDepth = curDepth;
17
res = cur.val;
18
}
19
dfs(cur.left, curDepth);
20
dfs(cur.right, curDepth);
21
}
22
}
Copied!
Python Code:
1
class Solution(object):
2
3
def __init__(self):
4
self.res = 0
5
self.max_level = 0
6
7
def findBottomLeftValue(self, root):
8
self.res = root.val
9
def dfs(root, level):
10
if not root:
11
return
12
if level > self.max_level:
13
self.res = root.val
14
self.max_level = level
15
dfs(root.left, level + 1)
16
dfs(root.right, level + 1)
17
dfs(root, 0)
18
19
return self.res
Copied!
Java Code:
1
class Solution {
2
int max = 0;
3
Map<Integer,Integer> map = new HashMap<>();
4
public int findBottomLeftValue(TreeNode root) {
5
if (root == null) return 0;
6
dfs(root,0);
7
return map.get(max);
8
}
9
10
void dfs (TreeNode node,int level){
11
if (node == null){
12
return;
13
}
14
int curLevel = level+1;
15
dfs(node.left,curLevel);
16
if (curLevel > max && !map.containsKey(curLevel)){
17
map.put(curLevel,node.val);
18
max = curLevel;
19
}
20
dfs(node.right,curLevel);
21
}
22
23
}
Copied!
CPP:
1
class Solution {
2
public:
3
int res;
4
int max_depth = 0;
5
void findBottomLeftValue_core(TreeNode* root, int depth) {
6
if (root->left || root->right) {
7
if (root->left)
8
findBottomLeftValue_core(root->left, depth + 1);
9
if (root->right)
10
findBottomLeftValue_core(root->right, depth + 1);
11
} else {
12
if (depth > max_depth) {
13
res = root->val;
14
max_depth = depth;
15
}
16
}
17
}
18
int findBottomLeftValue(TreeNode* root) {
19
findBottomLeftValue_core(root, 1);
20
return res;
21
}
22
};
Copied!
复杂度分析
- 时间复杂度：$O(N)$，其中 N 为树的节点总数。
- 空间复杂度：$O(h)$，其中 h 为树的高度。
最近更新 1yr ago