题目描述

给定一棵二叉树，请编写一个函数来返回其右视图。右视图是指从主视图的右边看，能看到的节点构成的视图。换句话说，从根节点开始，每一层中最右边的节点构成的视图即为右视图。

示例

考虑以下二叉树：

    1
   / \
  2   3
 /   / \
4   5   6

该树的右视图是 [1, 3, 6]。

解题思路

为了得到二叉树的右视图，我们可以使用广度优先搜索（BFS）来遍历二叉树的每一层，并在遍历每一层时记录最后一个访问的节点。这是因为BFS按层次遍历树，并且每次迭代都会处理当前层的所有节点，因此最后一个被处理的节点即为该层的最右节点。

示例代码

PHP

class TreeNode {
    public $val;
    public $left;
    public $right;
    
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

function rightSideView($root) {
    if ($root == null) return [];
    
    $queue = new SplQueue(); // 使用队列进行BFS
    $queue->enqueue($root);
    $result = [];
    
    while (!$queue->isEmpty()) {
        $levelSize = $queue->count();
        
        for ($i = 0; $i < $levelSize; $i++) {
            $node = $queue->dequeue();
            
            // 每层只取最后一个节点
            if ($i == $levelSize - 1) {
                $result[] = $node->val;
            }
            
            if ($node->left != null) $queue->enqueue($node->left);
            if ($node->right != null) $queue->enqueue($node->right);
        }
    }
    
    return $result;
}

Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def rightSideView(root):
    if not root:
        return []
    
    queue = [root]
    result = []
    
    while queue:
        level_size = len(queue)
        
        for _ in range(level_size):
            node = queue.pop(0)
            
            # 取每层的最后一个节点
            if _ == level_size - 1:
                result.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    
    return result

JavaScript

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

function rightSideView(root) {
    if (!root) return [];
    
    const queue = [root];
    const result = [];
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            
            // 取每层的最后一个节点
            if (i === levelSize - 1) {
                result.push(node.val);
            }
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
    }
    
    return result;
}

这些代码示例展示了如何使用BFS来找到二叉树的右视图。每种语言都遵循了相似的逻辑，即使用队列来按层遍历树，并只记录每一层最后一个节点的值。