广度优先遍历 BFS
解题思路
对二叉树进行层序遍历；
与以往不同的是遍历每一层的时候，从右向左放入节点，这样每一层的最左边的元素一定是在队列的最后一个；
出队的同时不断更新 res ，由于最左边的元素在队列的最后一个，则遍历完 res 就是二叉树最后一个层级最左边的元素值；
复杂度
-
时间复杂度：
O(n)，其中 n 是二叉树的节点数量； -
空间复杂度：
O(n)，最坏情况下退化成链，递归深度为 n；
实现代码
var findBottomLeftValue = function (root) {
let res = null;
let queue = [root];
while (queue.length) {
let node = queue.shift();
res = node.val;
node.right && queue.push(node.right);
node.left && queue.push(node.left);
}
return res;
};
深度优先遍历 DFS
解题思路
先声明一个最大深度 maxDepth 并初始化深度为 -Infinity；
再对二叉树进行 dfs 先序遍历；
由于先遍历的左节点，后遍历的右节点，那么每访问一层都是先访问的左节点，然后更新最大深度，更新 res ，则 res 是每一层的最左边的节点；
复杂度
-
时间复杂度：
O(n)，其中 n 是二叉树的节点数量； -
空间复杂度：
O(n)，最坏情况下退化成链，递归深度为 n；
实现代码
var findBottomLeftValue = function (root) {
const dfs = (root, depth) => {
if (root === null) return;
if (depth > maxDepth) {
res = root.val;
maxDepth = depth; // 更新最大深度
}
dfs(root.left, depth + 1);
dfs(root.right, depth + 1);
};
let res = null;
let maxDepth = -Infinity;
dfs(root, 1);
return res;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 142. 环形链表 II
上一篇
评论
