199. 二叉树的右视图(JS实现)

迈不过友情╰ 2022-11-25 11:41 57阅读 0赞

1 题目

给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。
示例:
输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:
1 <—
/
2 3 <—
\
5 4 <—

链接:https://leetcode-cn.com/problems/binary-tree-right-side-view

2 思路

这道题我们可以从对树进行中序遍历,但得先遍历树的右分支,再左分支,在遍历的过程中,记录每个节点的当前深度和当前遍历过程的最大深度,若当前节点的深度大于当前最大深度,说明该节点从右侧可以看见,则将其加入结果中

3代码

  1. /** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */
  2. /** * @param {TreeNode} root * @return {number[]} */
  3. var rightSideView = function(root) {
  4. let nums = [];
  5. if (!root) return nums;
  6. let stack = [];
  7. let p = root;
  8. let maxDepth = 0;
  9. let currentDepth = 0;
  10. while(p || stack.length > 0) {
  11. while(p) { //遍历节点的右分支
  12. currentDepth++;
  13. if (currentDepth > maxDepth) { //推入节点
  14. maxDepth++;
  15. nums.push(p.val);
  16. }
  17. stack.push([p, currentDepth]);
  18. p = p.right;
  19. }
  20. let node = stack.pop(); //回溯
  21. p = node[0].left; //对节点的左分支进行遍历
  22. currentDepth = node[1]; //当前深度也要回溯
  23. }
  24. return nums;
  25. };

发表评论

表情:
评论列表 (有 0 条评论,57人围观)

还没有评论,来说两句吧...

相关阅读