54 lines
1.5 KiB
JavaScript
54 lines
1.5 KiB
JavaScript
/**
|
||
* 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[]}
|
||
* https://leetcode.cn/problems/binary-tree-right-side-view/?envType=study-plan-v2&envId=top-interview-150
|
||
*/
|
||
const rightSideView = function (root) {
|
||
|
||
};
|
||
|
||
/*
|
||
按照题目要求，很容易想到利用层序遍历，将每一层的最后一个结果保存进 ans这个数组，最后返回ans就是我们所需要的答案
|
||
*/
|
||
|
||
function f1(root) {
|
||
const ans = []; // 储存结果的数组
|
||
const queue = []; // 层序遍历需要使用的队列
|
||
if (root) queue.push(root);
|
||
|
||
while (queue.length > 0) {
|
||
// 获取每一层的最后一个元素存入 ans
|
||
const n = queue.length;
|
||
ans.push(queue[n - 1].val);
|
||
|
||
// 将下一层元素压入队列
|
||
for (let i = 0; i < n; i++) {
|
||
const node = queue.shift();
|
||
if (node.left) {
|
||
queue.push(node.left);
|
||
}
|
||
if (node.right) {
|
||
queue.push(node.right);
|
||
}
|
||
}
|
||
}
|
||
|
||
return ans;
|
||
}
|
||
|
||
/*
|
||
思路2: 使用dfs优先遍右子树，将每一层遇到的第一个节点储存到一个map中，当遍历完所有元素，按照层数返回map中的值即可
|
||
过程：右子树DFS，如果当前节点不为空,查看这一层是否已经有元素了，如果没有那么这个值就是这一层的第一个元素，将他
|
||
加入映射,
|
||
*/
|
||
|
||
// TODO:
|