199. 二叉树的右视图

题目描述

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

示例 1:

输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

示例 2:

输入: [1,null,3]
输出: [1,3]

示例 3:

输入: []
输出: []

提示:

二叉树的节点个数的范围是 [0,100]
-100 <= Node.val <= 100

解法一：递归

如下是错误代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rightSideView(root *TreeNode) []int {
    var ans []int
    var dfs func(root *TreeNode)
    dfs = func(root *TreeNode) {
        if root == nil {
            return
        }
        ans = append(ans, root.Val)
        if root.Right != nil {
            dfs(root.Right)
        } else {
            dfs(root.Left)
        }
    }
    dfs(root)
    return ans
}

不能通过测试用例 [1, 2, 3, 4]，说明如果左子树的高度比右子树高且右子树不为空时会解答错误。如下为正确代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rightSideView(root *TreeNode) []int {
    // 定义 recur 为返回以 root 为根的二叉树的右视图的逆序
    var recur func(root *TreeNode) []int
    recur = func(root *TreeNode) []int {
        if root == nil {
            return []int{}
        }
        leftView, rightView := recur(root.Left), recur(root.Right)
        if len(rightView) >= len(leftView) {
            rightView = append(rightView, root.Val)
            return rightView
        } else {
            copy(leftView[len(leftView)-len(rightView):], rightView)
            leftView = append(leftView, root.Val)
            return leftView
        }
    }
    ans := recur(root)
    for i := 0; i < len(ans)/2; i++ {
        ans[i], ans[len(ans)-1-i] = ans[len(ans)-1-i], ans[i]
    }
    return ans
}

解法二：DFS

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rightSideView(root *TreeNode) []int {
    var ans []int
    var dfs func(root *TreeNode, depth int)
    dfs = func(root *TreeNode, depth int) {
        if root == nil {
            return
        }
        if depth >= len(ans) {
            ans = append(ans, root.Val)
        }
        ans[depth] = root.Val
        dfs(root.Left, depth+1)
        dfs(root.Right, depth+1)
    }
    dfs(root, 0)
    return ans
}

解法三：BFS

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rightSideView(root *TreeNode) []int {
    var ans []int
    if root == nil {
        return ans
    }
    var queue []*TreeNode
    queue = append(queue, root)
    for len(queue) > 0 {
        cnt := len(queue)
        for cnt > 0 {
            cur := queue[0]
            queue = queue[1:]
            if cnt == 1 {
                ans = append(ans, cur.Val)
            }
            if cur.Left != nil {
                queue = append(queue, cur.Left)
            }
            if cur.Right != nil {
                queue = append(queue, cur.Right)
            }
            cnt--
        }
    }
    return ans
}