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

package main

//BFS层序输出 右边第一个
func solve( xianxu []int ,  zhongxu []int ) []int {
    root := buildTree(xianxu, zhongxu)
    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 []int, inorder []int) *TreeNode {
    if len(preorder) == 0 || len(inorder) == 0 {
        return nil
    }

    root := &TreeNode{preorder[0] , nil , nil }     //根据前序，找到根节点，开始划分三部分

    i := 0
    for i = 0; i < len(inorder); i++ {
        if inorder[i] == preorder[0] {      //中序 在inorder找到 根结点（上文）== 递归的核心
            break
        }
    }

    root.Left = buildTree(preorder[1: len(inorder[:i]) + 1], inorder[:i])       //在中序【i】的左边
    root.Right = buildTree(preorder[len(inorder[:i]) + 1:], inorder[i+1:])     //在中序【i】的右边

    return root
}