题解 | #重建二叉树#
重建二叉树
https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6
package main
import (
. "nc_tools"
)
/*
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param preOrder int整型一维数组
* @param vinOrder int整型一维数组
* @return TreeNode类
*/
func reConstructBinaryTree(preOrder []int, vinOrder []int) *TreeNode {
// write code here
// 前序：根左右
// 中序：左根右
if len(preOrder) == 0 || len(vinOrder) == 0 {
return nil
}
//前序：[1,2,4,7,3,5,6,8]
//中序：[4,7,2,1,5,3,8,6]
root := &TreeNode{Val: preOrder[0]}
mid := findTargetIndex(vinOrder, preOrder[0])
root.Left = reConstructBinaryTree(preOrder[1:mid+1], vinOrder[:mid])
root.Right = reConstructBinaryTree(preOrder[mid+1:], vinOrder [mid+1:])
return root
}
func findTargetIndex(vinOrder []int, target int) int {
for key,value := range vinOrder{
if value == target {
return key
}
}
return -1
}
投递百度等公司8个岗位 >