LeetCode算法题(Go语言实现)_39

题目

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

一、代码实现

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

func rightSideView(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    
    var result []int
    queue := []*TreeNode{root}
    
    for len(queue) > 0 {
        levelSize := len(queue)
        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            
            if i == levelSize-1 {
                result = append(result, node.Val)
            }
            
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
    }
    return result
}

二、算法分析

1. 核心思路

• 层次遍历（BFS）：利用队列进行广度优先搜索，记录每层最后一个节点值
• 右视图特性：每层最右侧节点即为该层可见的节点

2. 关键步骤

1. 队列初始化：根节点入队
2. 层级遍历：记录当前层节点数，遍历时保留下一层节点
3. 右节点捕获：当遍历到当前层最后一个节点时记录值
4. 子节点入队：按顺序处理左右子节点

3. 复杂度

三、图解示例

四、边界条件与扩展

1. 特殊场景验证

• 空树：返回空数组
• 完全左斜树：返回根节点到最底层左节点的路径
• 单节点树：返回单个元素的数组

2. 多语言实现

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

class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        
        result = []
        queue = [root]
        
        while queue:
            level_size = len(queue)
            for i in range(level_size):
                node = queue.pop(0)
                if i == level_size - 1:
                    result.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return result

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                if (i == levelSize - 1) {
                    result.add(node.val);
                }
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        return result;
    }
}

五、总结与扩展

1. 核心创新点

• 层级遍历特性：利用BFS天然的分层特性获取右视图
• 高效判断逻辑：通过层级索引直接定位最右节点

2. 扩展应用

• 左视图：改为记录每层第一个节点
• 对角线视图：修改节点入队顺序和记录策略
• Z型遍历：结合层级奇偶性改变遍历方向

3. 工程优化

• 双向队列：使用Deque提升出队效率
• 层级缓存：预先缓存层级大小避免动态计算
• 内存优化：每层处理完后及时释放引用