leetcode 515 找树左下角的值
给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
示例1
输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]
示例2
输入: root = [1,2,3]
输出: [1,3]
思路
同样使用 bfs 的思想，把每一层的最大值用 map 记录，tree 遍历完毕之后，再去获取所有的 map 里面每层的最大值即可。
代码
/**
* 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)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var largestValues = function(root) {
if (root === null) {
return [];
}
const queue = [root];
const map = new Map();
root.level = 1;
map.set(1, root.val);
while (queue.length) {
const curr = queue.shift();
if (curr.left) {
queue.push(curr.left);
curr.left.level = curr.level + 1;
const currMax = map.get(curr.left.level) === undefined ? Number.MIN_SAFE_INTEGER : map.get(curr.left.level);
map.set(curr.left.level, Math.max(currMax, curr.left.val));
}
if (curr.right) {
queue.push(curr.right);
curr.right.level = curr.level + 1;
const currMax = map.get(curr.right.level) === undefined ? Number.MIN_SAFE_INTEGER : map.get(curr.right.level);
map.set(curr.right.level, Math.max(currMax, curr.right.val));
}
}
const res = [];
map.forEach((v) => {
res.push(v);
});
return res;
};
复杂度分析:
- 时间复杂度: O(LogN)
- 空间复杂度：O(N)