题解 | #输出二叉树的右视图#

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 求二叉树的右视图
 * @param xianxu int整型一维数组 先序遍历
 * @param zhongxu int整型一维数组 中序遍历
 * @return int整型一维数组
*/
func solve( xianxu []int ,  zhongxu []int ) []int {
    // write code here
    pre, mid := xianxu, zhongxu
	root := buildTree(pre, mid)
	return floorTravel(root)
}

func buildTree(pre, mid []int) *TreeNode {
	if len(pre) == 0 {
		return nil
	}
	root := &TreeNode{Val: pre[0]}
	pos := findPos(mid, pre[0])
	root.Left = buildTree(pre[1:len(pre[:pos])+1], mid[:pos])
	root.Right = buildTree(pre[len(pre[:pos])+1:], mid[pos+1:])
	return root
}

func findPos(arr []int, num int) int {
	for i, val := range arr {
		if val == num {
			return i
		}
	}
	return -1
}

func floorTravel(node *TreeNode) []int {
	if node == nil {
		return nil
	}
	floor := make([]*TreeNode, 0)
	floor = append(floor, node)
	res := make([]int, 0)
	for len(floor) != 0 {
		size := len(floor)
		tmp := make([]*TreeNode, 0)
		for i := 0; i < size; i++ {
			curr := floor[0]
			floor = floor[1:]
			if curr.Left != nil {
				tmp = append(tmp, curr.Left)
			}
			if curr.Right != nil {
				tmp = append(tmp, curr.Right)
			}
			if i == size-1 {
				res = append(res, curr.Val)
			}
		}
		floor = tmp
	}
	return res
}