二叉树的右视图

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

示例:

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

解释:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-right-side-view

一开始以为是简单的打印右子数的值，果然是错的，右视图即代表最右侧的值。

想法：

• 把每层的节点都遍历出来，取最右→_→，放入结果集中，然后到下一层。

  • 其中node的存、取，可以用栈结构来实现，比如在同一层中，将所有node从左到右依次放入一个数组childrenStack，那数组的最后一个值就是最右本右→_→
  • 可到下一层，又需根据上一层的各个node节点作为父节点，去找他们各自的子节点，怎么找呢？

  这里思路是BFS，但又往层深（DFS）上想了下，结果绕进去了。。

• 回来，想到可以再用一个队列去存这个每层的任务父节点，比如叫taskQueue，操作完本层后，本层的所有子节点都将作为下一层的父节点，即queue=childrenStack

  • 起始条件：最初将root这个根节点放入taskQueue中
  • 终止条件：queue全部为空

• 于是，我们只要围绕taskQueue进行遍历，每层处理完后，再将本层节点更新为taskQueue，直到最后为空，循环结束。

代码：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rightSideView(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	var result []int
	result = append(result, root.Val)

	var taskQueue []*TreeNode
	taskQueue = append(taskQueue,root)

	for len(taskQueue) > 0 {
		var stack []*TreeNode
		for _, node := range taskQueue {
			if node == nil {
				continue
			}
			if node.Left != nil {
				stack = append(stack, node.Left)
			}
			if node.Right != nil {
				stack = append(stack, node.Right)
			}
		}
		taskQueue = stack
		if len(stack)>0{
			right := stack[len(stack)-1]
			result = append(result, right.Val)
		}
	}
	return result
}

• 时间复杂度O(n)因为遍历所有节点1次。
• 空间复杂度O(n)

回顾 这算是BFS广度优先算法的一种实现，那么DFS深度优先算法可以搞吗？有的：

• 每层必定有结果，且只有一个结果
• 从层深可判断当前层是否已有结果

代码

func rightSideViewV2(root *TreeNode) []int {
	result := []int{}
	helper(root,&result,0)
	return result
}

func helper(root *TreeNode,result *[]int,deep int){
	if root == nil{
		return
	}
	if deep == len(*result){
		*result = append(*result, root.Val)
	}
	helper(root.Right,result,deep+1)
	helper(root.Left,result,deep+1)
}

• 时间复杂度O(n)，因为这个做法也需要遍历所有节点1次。
• 空间复杂度O(n)，因为递归深度最坏与树深度接近，树深度可能达到O(n）