https://leetcode-cn.com/problems/find-bottom-left-tree-value/
给定一个二叉树，在树的最后一行找到最左边的值。
示例 1:
输入:
2
/ \
1 3
输出:
1
示例 2:
输入:
1
/ \
2 3
/ / \
4 5 6
/
7
输出:
7
注意: 您可以假设树（即给定的根节点）不为 NULL。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-bottom-left-tree-value
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
按照题目意思我们只需要找到最后一层，返回最左边的节点即可。
所以只要对二叉树进行层次遍历，等遍历到最后一层的时候，返回第一个节点。
层次遍历模板 1：
新建 curLevel 数组保存当前层的节点；
新建 nextLevel 数组保存下一层要遍历的节点；
将 root 加入到 curLevel 中，开始遍历；
重复以下操作：
遍历 curLevel 中的节点：
如果该节点存在左子节点，把左子节点加入到 nextLevel 中；
如果该节点存在右子节点，把右子节点加入到 nextLevel 中；
判断 nextLevel 中是否有节点：
如果没有，说明已经遍历到树的最深层次，此时 curLevel 中放的是最深层的所有叶子节点，返回第一个即可；
让 nextLevel 作为下一个循环中要遍历的对象，即 curLevel = nextLevel；
将 nextLevel 清空；
层次遍历模板 2：
const queue = [root];
while (queue.length) {
// 先记录这一层的节点数
let len = queue.length;
while (len--) {
const node = queue.shift();
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
}JavaScript Code
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var findBottomLeftValue = function (root) {
let curLevel = [root],
nextLevel = [];
while (true) {
for (let node of curLevel) {
node.left && nextLevel.push(node.left);
node.right && nextLevel.push(node.right);
}
if (!nextLevel.length) return curLevel[0].val;
curLevel = nextLevel;
nextLevel = [];
}
};Python Code
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def findBottomLeftValue(self, root):
"""
:type root: TreeNode
:rtype: int
"""
curLevel, nextLevel = [root], []
while True:
for node in curLevel:
if node.left: nextLevel.append(node.left)
if node.right: nextLevel.append(node.right)
if not nextLevel: return curLevel[0].val
curLevel, nextLevel = nextLevel, []JavaScript Code
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var findBottomLeftValue = function (root) {
if (!root) return 0;
const queue = [root];
let bottomLeft = null;
while (queue.length) {
let len = queue.length;
// 每遍历一层就更新一次最左节点
// 最后一层更新就是最后一层的的最左节点
bottomLeft = queue[0];
while (len--) {
const node = queue.shift();
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
}
return bottomLeft.val;
};C++ Code
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
TreeNode* bottom_left = nullptr;
queue<TreeNode*> level;
level.push(root);
while (!level.empty()) {
int size = level.size();
bottom_left = level.front();
while (size--) {
TreeNode* node = level.front();
level.pop();
if (node->left) level.push(node->left);
if (node->right) level.push(node->right);
}
}
return bottom_left->val;
}
};- 时间复杂度：$O(N)$，其中 N 为节点数。
- 空间复杂度:
$O(q)$ ，q 为队列长度。最坏情况是满二叉树，此时 q 为$2/N$ ，即为$O(N)$ ，N 为二叉树节点数。
想一下递归的路线，如果我们先递归遍历左子树再遍历右子树，那么每遍历到新一层的时候，都是先访问最左边的节点。
- 所以我们只需要在遍历到新一层的时候，记录第一个节点。
- 用
depth来记录当前层次，用maxDepth来记录已经遍历过的最深层次，当depth > maxDepth的时候，说明遍历到了新层次：- 记录第一个节点的值
- 更新
maxDepth
创建 ans 来记录遍历中遇到的最左边的子节点
创建 maxDepth 来记录已经遍历到的最深层次
定义一个 dfs 函数来遍历二叉树，函数接收 (node, depth) 两个参数，node 是当前遍历到的节点，depth 是当前遍历深度：
如果 node 为 null，终止遍历
// 因为我们是先遍历左子节点，再遍历右子节点
// 所以第一次 depth > maxDepth 的时候，遍历到的就是 depth 这一层最左边的子节点
// 接着我们更新 maxDepth，之后遍历同一 depth 的节点时，ans 都不会更新了
如果当前层级 depth > maxDepth：
更新 ans 为 node.val
更新 maxDepth 为 depth
// 分别递归遍历左右子树
dfs(node.left, depth + 1)
dfs(node.right, depth + 1)
调用 dfs 函数，传入 (root, 0)
返回 ans
- 时间复杂度：$O(N)$，其中 N 为节点数。
- 空间复杂度：$O(h)$，其中
$h$ 为树的深度，最坏的情况$h$ 等于$N$ ，其中 N 为节点数，此时树退化到链表。
JavaScript Code
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var findBottomLeftValue = function (root) {
let maxDepth = 0;
let ans = 0;
helper(root, 1);
return ans;
// ******************************
function helper(root, depth) {
if (!root) return 0;
if (depth > maxDepth) {
maxDepth = depth;
ans = root.val;
}
helper(root.left, depth + 1);
helper(root.right, depth + 1);
}
};Python Code
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
_ans = 0
_maxDepth = 0
def helper(self, root, depth):
if root is None: return 0
if depth > self._maxDepth:
self._maxDepth = depth
self._ans = root.val
self.helper(root.left, depth + 1)
self.helper(root.right, depth + 1)
def findBottomLeftValue(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.helper(root, 1)
return self._ansC++ Code
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
findBottomLeftValue(root, 1);
return ans_;
}
void findBottomLeftValue(TreeNode* root, int depth) {
if (depth > max_depth_) {
max_depth_ = depth;
ans_ = root->val;
}
if (root->left) findBottomLeftValue(root->left, depth + 1);
if (root->right) findBottomLeftValue(root->right, depth + 1);
}
private:
int max_depth_ = 0;
int ans_;
};