題目

給定一棵二叉樹，想象自己站在它的右側(cè)，按照從頂部到底部的順序，返回從右側(cè)所能看到的節(jié)點(diǎn)值。

示例:

輸入: [1,2,3,null,5,null,4]
輸出: [1, 3, 4]
解釋:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

思路

1. dfs 深度優(yōu)先

因?yàn)橐蟮氖怯乙晥D, 所以和二叉樹的先序遍歷相反就可以了, 根節(jié)點(diǎn) --> 右節(jié)點(diǎn) --> 左節(jié)點(diǎn), 把每一層的第一個(gè)訪問到的節(jié)點(diǎn)加入到返回?cái)?shù)組中

2. bfs 廣度優(yōu)先

利用廣度優(yōu)先對(duì)每層進(jìn)行便利, 記錄下每層的最有一個(gè)元素即可

兩種時(shí)間復(fù)雜度都是O(n)

code

go

dfs

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var res []int

func rightSideView(root *TreeNode) []int {
    res = []int{}
    dfs(root, 1)
    return res
}

func dfs(root *TreeNode, level int) {
    if root == nil {
        return
    }

    if level > len(res) {
        res = append(res, root.Val)
    }

    dfs(root.Right, level+1)
    dfs(root.Left, level+1)
}

bfs

func rightSideView(root *TreeNode) []int {
    var res []int
      if root == nil{
        return res
    }
    var queue = []*TreeNode{root}
    var level int
    for 0 < len(queue) {
        length := len(queue)
        for 0 < length {
            length--
            if len(res) == level {
                res = append(res, queue[0].Val)
            }
            if queue[0].Right != nil {
                queue = append(queue, queue[0].Right)
            }
            if queue[0].Left != nil {
                queue = append(queue, queue[0].Left)
            }

            queue = queue[1:]
        }
        level++
    }
    return res
}