leetcode-119-二叉树的右视图

题目

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

示例:

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

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

思路

1. dfs 深度优先

因为要求的是右视图, 所以和二叉树的先序遍历相反就可以了, 根节点 --> 右节点 --> 左节点, 把每一层的第一个访问到的节点加入到返回数组中

2. bfs 广度优先

利用广度优先对每层进行便利, 记录下每层的最有一个元素即可

两种时间复杂度都是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
}