题解 | #重建二叉树#

using System;
using System.Collections.Generic;

/*
public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode (int x)
    {
        val = x;
    }
}
*/

class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pre int整型一维数组 
     * @param tin int整型一维数组 
     * @return TreeNode类
     */
    public TreeNode reConstructBinaryTree (List<int> pre, List<int> vin) {
        // write code here
        if (pre.Count > 0 && vin.Count > 0){
            TreeNode root = new TreeNode(pre[0]);
            List<int> preLeftList = new List<int>();
            List<int> vinLeftList = new List<int>();
            List<int> preRightList = new List<int>();
            List<int> vinRightList = new List<int>();
            int rootIndex = vin.IndexOf(pre[0]);
            // 拆分前序序列
            for(int i=1; i< pre.Count; i++){
                if(i<=rootIndex){
                    preLeftList.Add(pre[i]);
                }else{
                    preRightList.Add(pre[i]);
                }
            }
            // 拆分中前序序列
            for(int i=0; i< vin.Count; i++){
                if(i<rootIndex){
                    vinLeftList.Add(vin[i]);
                }else if(i>rootIndex){
                    vinRightList.Add(vin[i]);
                }
            }
            root.left = reConstructBinaryTree(preLeftList, vinLeftList);
            root.right = reConstructBinaryTree(preRightList, vinRightList);
            return root;
        }else{
            return null;
        }
        
    }
}