# 找树左下角的值（513）
# 题目
给定一个二叉树，在树的最后一行找到最左边的值。
# 示例
输入:
2
/ \
1 3
1
2
3
2
3
输出:
1
输入:
1
/ \
2 3
/ / \
4 5 6
/
7
1
2
3
4
5
6
7
2
3
4
5
6
7
输出:
7
# 注意
您可以假设树（即给定的根节点）不为 NULL。
# 算法
# 广度优先算法
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
export const findBottomLeftValue = (root) => {
if (!root) return root;
let res = 0;
const queue = [root];
while (queue.length) {
res = queue[0].val;
const leng = queue.length;
for (let i = 0; i < leng; i++) {
const curNode = queue.shift();
if (curNode.left) queue.push(curNode.left);
if (curNode.right) queue.push(curNode.right);
}
}
return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 深度优先算法
维护一个深度res[0]，我们使用前序遍历，当当前深度第一次大于res[0]的时候，当前值一定是新的深度的最左边的值，我们将其保存最后作为结果返回
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
export const findBottomLeftValue = (root) => {
let res = [0, root.val];
let dep = 0;
const rec = (root, dep) => {
if (root.left) rec(root.left, dep + 1);
if (dep > res[0]) res = [dep, root.val];
if (root.right) rec(root.right, dep + 1);
};
rec(root, dep);
return res[1];
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19