题解 | #重建二叉树#

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 preOrder int整型一维数组
     * @param vinOrder int整型一维数组
     * @return TreeNode类
     */
    List<int> preorder;
    IDictionary<int,int> inorderh = new Dictionary<int,int>();
    public TreeNode reConstructBinaryTree (List<int> preOrder, List<int> vinOrder) {
        //preorder 计数
        //inorder 寻找root并计算左右子树长度
        this.preorder = preOrder;
        for (int i = 0; i < vinOrder.Count; i++) {
            inorderh.Add(vinOrder[i], i);
        }
        //if(preorder.Length == 1) return new TreeNode(preorder[0]);
        return DeduceTree2(0, 0, preorder.Count - 1);
    }
    public TreeNode DeduceTree2(int root, int left, int right) {
        if (left > right) return null;
        TreeNode node = new TreeNode(preorder[root]);
        int leftLength = inorderh[preorder[root]] - left;
        node.left = DeduceTree2(root + 1, left, left + leftLength - 1);
        node.right = DeduceTree2(root + leftLength + 1, left + leftLength + 1, right);
        return node;
    }
}