199 二叉树的右视图

题目描述#

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

思路#

站在右侧看二叉树，每一层只能看到最右边的那个节点。因此问题转化为：找出每一层的最后一个节点。

用 BFS 层序遍历，每次处理一整层的节点。遍历时记录当前层的节点总数 queueSize，当某个节点是该层第 queueSize-1 个（即最后一个）时，将其值加入结果。

处理每个节点时，依次把它的左、右子节点加入队列，这样下一层的顺序也保持从左到右，最后一个出队的自然是最右边的节点。

代码#

BFS 层序遍历#

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rightSideView(root *TreeNode) []int {
    // 需要用一个队列去保存一个层的顺序
    ans := make([]int, 0)
    if root == nil {
        return ans
    }
    queue := make([]*TreeNode, 0)
    queue = append(queue, root)
    for len(queue) != 0 {
        queueSize := len(queue)
        // 遍历每层
        for i := 0; i < queueSize; i++ {
            node := queue[0]
            queue = queue[1:]
            if i == queueSize-1 {
                ans = append(ans, node.Val)
            }
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
    }
    return ans
}

DFS 深度优先遍历#

用递归 DFS 也能解这道题。关键观察是：ans 的长度代表当前已记录的层数，如果当前节点的深度 depth 等于 len(ans)，说明这一层还没有记录过节点，当前节点就是该层第一个被访问到的节点。

递归时先走右子树、再走左子树，保证每层第一个访问到的节点一定是最右边的那个。这样只要 depth == len(ans) 时追加即可，不需要额外判断。

func rightSideView(root *TreeNode) (ans []int) {
    var dfs func(*TreeNode, int)
    dfs = func(node *TreeNode, depth int) {
        if node == nil {
            return
        }

        if depth == len(ans) {
            ans = append(ans, node.Val)
        }
        dfs(node.Right, depth+1) //保证首次遇到的是最右边的节点
        dfs(node.Left, depth+1)
    }
    dfs(root, 0)
    return
}