0199. Binary Tree Right Side View

199. Binary Tree Right Side View #

题目 #

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example:


Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:

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

题目大意 #

从右边看一个树,输出看到的数字。注意有遮挡。

解题思路 #

  • 这一题是按层序遍历的变种题。按照层序把每层的元素都遍历出来,然后依次取每一层的最右边的元素即可。用一个队列即可实现。
  • 第 102 题和第 107 题都是按层序遍历的。

代码 #


package leetcode

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


⬅️上一页

下一页➡️

Calendar Sep 6, 2020
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者