题目

题目链接：
https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6

思路

先序遍历第一个值就是根节点，根据这个值可以在中序中划分左右子树，
我们这里已经将一个数划分成两颗子树，那么在递归的使用刚刚的分析可以继续分开，
直到叶子节点。

参考答案Java

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param preOrder int整型一维数组
     * @param vinOrder int整型一维数组
     * @return TreeNode类
     */
    public TreeNode reConstructBinaryTree (int[] preOrder, int[] vinOrder) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < vinOrder.length ; i++) {
            map.put(vinOrder[i], i);
        }
        return f1(preOrder, 0, preOrder.length - 1, vinOrder, 0, vinOrder.length - 1,
                  map);
    }

    public TreeNode f1(int[] pre, int l1, int r1, int[] in, int l2, int r2,
                       Map<Integer, Integer> map) {
        if (l1 > r1) return null;
        if (l1 == r1) return new TreeNode(pre[l1]);
        else {
            TreeNode root = new TreeNode(pre[l1]);
            int index = map.get(pre[l1]);
            root.left = f1(pre, l1 + 1, l1 + index - l2, in, l2, index - 1, map);
            root.right = f1(pre, l1 + index - l2 + 1, r1, in, index + 1, r2, map);
            return root;
        }
    }
}

参考答案Go

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 {
	indexMap := map[int]int{}
	for i := 0; i < len(vinOrder); i++ {
		indexMap[vinOrder[i]] = i
	}

	return dfs(preOrder, 0, len(preOrder)-1, vinOrder, 0, len(vinOrder)-1, indexMap)
}

func dfs(preOrder []int, l1 int, r1 int, vinOrder []int, l2 int, r2 int, imap map[int]int) *TreeNode {
	if l1 > r1 {
		return nil
	}

	 if l1 == r1 {
		return &TreeNode{preOrder[l1], nil, nil}
	}

	root := &TreeNode{preOrder[l1], nil, nil}
	index,_ := imap[preOrder[l1]]

	root.Left = dfs(preOrder, l1+1, l1+index-l2, vinOrder, l2, index-1, imap)
	root.Right = dfs(preOrder, l1+index-l2+1, r1, vinOrder, index+1, r2, imap)

	return root
}

参考答案PHP

<?php

/*class TreeNode{
    var $val;
    var $left = NULL;
    var $right = NULL;
    function __construct($val){
        $this->val = $val;
    }
}*/

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param preOrder int整型一维数组 
 * @param vinOrder int整型一维数组 
 * @return TreeNode类
 */
function reConstructBinaryTree( $preOrder ,  $vinOrder )
{
 $imap =array();
    for($i=0;$i<count($vinOrder);$i++){
        $imap[$vinOrder[$i]] = $i;
    }

    return dfs($preOrder,0,count($preOrder)-1,$vinOrder,0,count($vinOrder)-1,$imap);
}

function dfs($pre,$l1,$r1,$in,$l2,$r2,$imap){
    if($l1>$r1) return null;
    if($l1==$r1) return new TreeNode($pre[$l1]);
    $root = new TreeNode($pre[$l1]);
    $index = $imap[$pre[$l1]];
    $root->left = dfs($pre,$l1+1,$l1+$index-$l2,$in,$l2,$index-1,$imap);
    $root->right = dfs($pre,$l1+$index-$l2+1,$r1,$in,$index+1,$r2,$imap);
    return $root;
}