LeetCode 199 二叉树右侧视角图

1 题目描述

给定一个二叉树,想象站在其右侧,返回以该视角看到的自上而下的节点值。

例子1:

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

输出:[1, 3, 4]

释义:

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

题目出处:LeetCode

2 解决思路

该题目要求的是列出二叉树每一层的最右节点。

我们递归对树进行后序遍历,若当前层未遍历过,则将该节点记录。这样每一层最先遍历到的即是最右节点。

当整个树遍历完成时,即返回所有最右节点。

3 Golang实现代码

https://github.com/olzhy/

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

func postOrderTraversal(root *TreeNode, depth int, r *[]int) {
    if len(*r) < depth {
        *r = append(*r, root.Val)
    }
    if nil != root.Right {
        postOrderTraversal(root.Right, depth+1, r)
    }
    if nil != root.Left {
        postOrderTraversal(root.Left, depth+1, r)
    }
}

func rightSideView(root *TreeNode) []int {
    if nil == root {
        return []int{}
    }
    r := []int{root.Val}
    postOrderTraversal(root, 1, &r)
    return r
}
若觉得文章对您有所帮助,可以请我喝杯咖啡,Thanks!
微信 支付宝