学习记录：js算法（五十）：二叉树的右视图

文章目录

- 二叉树的右视图
- - 我的思路
  - 网上思路
- 总结

二叉树的右视图

给定一个二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

图一：
在这里插入图片描述

示例 1:如图一
输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

示例 2:
输入: [1,null,3]
输出: [1,3]

示例 3:
输入: []
输出: []

我的思路
循环
网上思路
递归

我的思路

var rightSideView = function(root) {
    if (root === null) return [];
    
    let queue = [root];
    let result = [];
    
    while (queue.length > 0) {
        let size = queue.length;
        for (let i = 0; i < size; i++) {
            let currentNode = queue.shift();
            
            // 将左右子节点加入队列
            if (currentNode.left) queue.push(currentNode.left);
            if (currentNode.right) queue.push(currentNode.right);
            
            // 如果是当前层的最后一个节点，将其值加入结果数组
            if (i === size - 1) {
                result.push(currentNode.val);
            }
        }
    }
    
    return result;
};

讲解
要在二叉树中获取从右视图看到的节点值，我们可以使用层次遍历（广度优先搜索 BFS）的方法，同时跟踪每一层的最后一个节点。这样，我们就可以收集到每一层最右边的节点值。

初始化：创建一个队列 queue 并将根节点 root 加入队列。同时创建一个空数组 result 用于存放结果。
层次遍历：进行层次遍历，使用一个循环，只要队列不为空就一直运行。在每次循环开始时，记录当前队列的大小 size，这代表了当前层的节点数。
处理当前层节点：在当前层中，依次从队列中取出节点，将其左右子节点加入队列。同时，记录下当前层的最后一个节点的值，即为当前层的右视图节点。
更新结果：将当前层的右视图节点值添加到结果数组 result 中。
重复步骤3和4，直到队列为空，即所有节点都被处理完毕。
返回结果：返回结果数组 result，它包含了从右视图看到的节点值。

网上思路

var rightSideView = function (root) {
    const result = []; // 存储结果

    function dfs(node, level) {
        if (!node) return; // 如果节点为空，返回

        // 如果当前层级的结果数组没有值，说明是第一次访问这一层
        if (result.length === level) {
            result.push(node.val); // 记录当前节点的值
        }

        // 先遍历右子树，再遍历左子树
        dfs(node.right, level + 1);
        dfs(node.left, level + 1);
    }

    dfs(root, 0); // 从根节点开始DFS
    return result; // 返回从右侧看到的节点值
}

讲解

rightSideView 函数：定义一个结果数组 result，并调用递归函数 dfs。
递归函数 dfs：
检查当前节点是否为空，如果为空则返回。
如果当前层级的结果数组还没有值，说明这是第一次访问这一层，将当前节点的值加入结果。
先递归访问右子树，再访问左子树，以保证优先访问右侧节点。