二叉树的右视图：BFS与DFS实现方法详解 | 算法教程

二叉树的右视图是指从二叉树的右侧看过去，能看到的节点序列。具体来说，就是从每一层的最右侧节点开始，依次输出这些节点的值。

问题分析

要解决这个问题，我们需要遍历二叉树的每一层，并记录每一层的最右侧节点。通常可以使用广度优先搜索（BFS）或深度优先搜索（DFS）来实现。

方法一：广度优先搜索（BFS）

BFS 是一种逐层遍历的方法，我们可以通过队列来实现。具体步骤如下：

1. 使用队列来存储每一层的节点。
2. 遍历每一层时，记录当前层的节点数，并将每一层的最后一个节点加入到结果中。

function rightSideView(root) {
    if (!root) return [];
    
    const result = [];
    const queue = [root];
    
    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;
}

方法二：深度优先搜索（DFS）

DFS 是一种递归遍历的方法，我们可以通过递归来遍历每一层，并记录每一层的最右侧节点。

1. 使用递归遍历二叉树，记录当前深度。
2. 如果当前深度等于结果数组的长度，说明当前节点是该层的最右侧节点，将其加入结果数组。

function rightSideView(root) {
    const result = [];
    
    function dfs(node, depth) {
        if (!node) return;
        
        // 如果当前深度等于结果数组的长度，说明当前节点是该层的最右侧节点
        if (depth === result.length) {
            result.push(node.val);
        }
        
        // 先遍历右子树，再遍历左子树
        dfs(node.right, depth + 1);
        dfs(node.left, depth + 1);
    }
    
    dfs(root, 0);
    return result;
}

复杂度分析

• 时间复杂度：两种方法的时间复杂度都是 O(N)，其中 N 是二叉树的节点数。每个节点都会被访问一次。
• 空间复杂度：
  • BFS 的空间复杂度取决于队列的大小，最坏情况下是 O(N)。
  • DFS 的空间复杂度取决于递归栈的深度，最坏情况下是 O(N)。

总结

• BFS 更适合层序遍历的场景，代码直观且易于理解。
• DFS 通过递归实现，代码简洁，但需要理解递归的深度优先特性。

根据具体场景和需求，可以选择合适的方法来实现二叉树的右视图。