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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 求二叉树的右视图
 * @param xianxu int整型一维数组 先序遍历
 * @param zhongxu int整型一维数组 中序遍历
 * @return int整型一维数组
*/
//BFS（只输出最右边的节点）
func solve(preorder []int, inorder []int) []int {
	root := buildTree(preorder, inorder)
	if root == nil {
		return []int{}
	}

	queue := []*TreeNode{root}
	levels := []int{}

	for len(queue) > 0 {
		n := len(queue)

		for i := 0; i < n; i++ {
			root = queue[0]
			queue = queue[1:]

			if root.Left != nil {
				queue = append(queue, root.Left)
			}
			if root.Right != nil {
				queue = append(queue, root.Right)
			}

			if i == n-1 {
				levels = append(levels, root.Val)
			}
		}
	}
	return levels
}
//构造二叉树
func buildTree(preorder, inorder []int) *TreeNode {
	return build(preorder, 0, len(preorder)-1, inorder, 0, len(inorder)-1)
}
func build(preorder []int, preStart, preEnd int, inorder []int, inStart, inEnd int) *TreeNode {
	if preStart > preEnd {
		return nil
	}
	rootVal := preorder[preStart]
	index := 0
	for i := inStart; i <= inEnd; i++ {
		if rootVal == inorder[i] {
			index = i
			break
		}
	}
	root := &TreeNode{Val: rootVal}
	leftSize := index - inStart
	root.Left = build(preorder, preStart+1, preStart+leftSize, inorder, inStart, index-1)
	root.Right = build(preorder, preStart+leftSize+1, preEnd, inorder, index+1, inEnd)
	return root
}