Tree - 199. Binary Tree Right Side View

22

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       <---

思路:

题目意思是返回树最右边一个不空的节点的值,采用广度优先遍历,遍历每一层,找出最右边的一个节点就可以。

代码:

go:

/**

 * Definition for a binary tree node.

 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rightSideView(root *TreeNode) []int {
     var (
        res []int
        
        curQ = []*TreeNode{root}
        nextQ []*TreeNode
    )
    
    if root == nil {
        return res
    }
    
    for len(curQ) != 0 {
        res = append(res, curQ[len(curQ) - 1].Val)
        
	for len(curQ) != 0 {
            cur := curQ[0]
            curQ = curQ[1:]
            if cur.Left != nil {
                nextQ = append(nextQ, cur.Left)
            }
            if cur.Right != nil {
                nextQ = append(nextQ, cur.Right)
            }
        }

        curQ = nextQ
        nextQ = nil
    }
    
    return res
}