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

package main

import (
	. "nc_tools"
)

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 求二叉树的右视图
 * @param preOrder int整型一维数组 先序遍历
 * @param inOrder int整型一维数组 中序遍历
 * @return int整型一维数组
 */
func solve(preOrder []int, inOrder []int) []int {
	// write code here
	if len(preOrder) == 0 || len(inOrder) == 0 {
		return nil
	}
	root := reConstructTree(preOrder, inOrder)
	var result []int
	queue := []*TreeNode{root}
	for len(queue) > 0 {
		levelLegth := len(queue)
		for i := 0; i < levelLegth; i++ {
			node := queue[0]
			queue = queue[1:]
			if i == levelLegth-1 {
				result = append(result, node.Val)
			}

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

	}
	return result
}

func reConstructTree(preOrder []int, inOrder []int) *TreeNode {
    if len(preOrder) == 0 || len(inOrder) == 0 {
        return nil
    }
	root := &TreeNode{Val: preOrder[0]}
	mid := findTargetIndex(inOrder, preOrder[0])
	root.Left = reConstructTree(preOrder[1:mid+1], inOrder[0:mid])
	root.Right = reConstructTree(preOrder[mid+1:], inOrder[mid+1:])
	return root
}

func findTargetIndex(inOrder []int, target int) int {
	for key, value := range inOrder {
		if value == target {
			return key
		}
	}
	return -1
}