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

package main

import (
	"container/list"
    . "nc_tools"
)

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 求二叉树的右视图
 * @param preOrder int整型一维数组 先序遍历
 * @param inOrder int整型一维数组 中序遍历
 * @return int整型一维数组
 */
func solve( preOrder []int ,  inOrder []int ) []int {
    //创建一个map记录中序遍历索引和值对应的关系
    index:=make(map[int]int,len(preOrder))
    for i:=range inOrder{
        index[inOrder[i]]=i
    }
    root:=buildTree(preOrder, 0, len(preOrder)-1, inOrder, 0, len(preOrder)-1, index)
    //对其进行BFS
    var nums []int
    //创建一个队列,头进尾出
    ll:=list.New()
    ll.PushFront(root)
    for ll.Len()>0{
        l:=ll.Len()
        var ele *list.Element
        for l>0{
            //取出节点
            ele=ll.Back()
            if ele.Value.(*TreeNode).Left!=nil{
                ll.PushFront(ele.Value.(*TreeNode).Left)
            }
            if ele.Value.(*TreeNode).Right!=nil{
                ll.PushFront(ele.Value.(*TreeNode).Right)
            } 
            ll.Remove(ele)
            l--
        }
        nums=append(nums, ele.Value.(*TreeNode).Val)
    }
    return nums
}



func buildTree(preOrder []int, preStart, preEnd int, inOrder []int, inStart, inEnd int, index map[int]int)*TreeNode{
    if preStart>preEnd||inStart>inEnd{
        return nil
    }
    //创建根节点
    root:=&TreeNode{
        Val: preOrder[preStart],
    }
    //获取中序遍历的根节点的索引
    inIndex:=index[preOrder[preStart]]
    le:=inIndex-inStart
    root.Left=buildTree(preOrder, preStart+1, preStart+le, inOrder, inStart, inIndex-1,index)
    root.Right=buildTree(preOrder, preStart+1+le, preEnd, inOrder, inIndex+1, inEnd, index)
    return root
}