二叉树的右视图

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

示例:

输入: [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)