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

思路：上一题的从先序和中序重建二叉树可以直接拿来用，得到二叉树后层序遍历，输出每一层的最后一个元素即可。

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 求二叉树的右视图
 * @param xianxu int整型一维数组 先序遍历
 * @param zhongxu int整型一维数组 中序遍历
 * @return int整型一维数组
*/
func solve(xianxu []int, zhongxu []int) []int {
	// write code here
	var res []int
	node := reConstructBinaryTree(xianxu, zhongxu)
	levelOrderSlice := levelOrder(node)
	for i := 0; i < len(levelOrderSlice); i++ {
		res = append(res, levelOrderSlice[i][len(levelOrderSlice[i])-1])
	}
	return res
}
func reConstructBinaryTree(pre []int, vin []int) *TreeNode {
	// write code here
	if length := len(pre); length == 0 {
		return nil
	}
	i := 0
	for i = 0; i < len(vin); i++ {
		if vin[i] == pre[0] {
			break
		}
	}
	root := &TreeNode{pre[0], nil, nil}
	root.Left = reConstructBinaryTree(pre[1:i+1], vin[:i])
	root.Right = reConstructBinaryTree(pre[i+1:], vin[i+1:])
	return root
}
func levelOrder(root *TreeNode) [][]int {
	result := make([][]int, 0)
	var dfs func(*TreeNode, int)
	dfs = func(node *TreeNode, level int) {
		if node == nil {
			return
		}
		if level == len(result) {
			result = append(result, []int{})
		}
		result[level] = append(result[level], node.Val)
		dfs(node.Left, level+1)
		dfs(node.Right, level+1)
	}
	dfs(root, 0)
	return result
}