题目描述

样例

给定：
前序遍历是：[3, 9, 20, 15, 7]
中序遍历是：[9, 3, 15, 20, 7]

返回：[3, 9, 20, null, null, 15, 7, null, null, null, null]
返回的二叉树如下所示：
    3
   / \
  9  20
    /  \
   15   7

理解

我觉得把中序排序左边的，右边的个数单独写出来利于理解。

JAVA 代码

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    Map<Integer,Integer> m = new HashMap();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int len = preorder.length;
        for(int i=0;i<inorder.length;i++) m.put(inorder[i],i);
        return dfs(preorder,inorder,0,len - 1,0,len - 1);
    }
    public TreeNode dfs(int[] preorder,int[] inorder,int pl,int pr,int il,int ir){
        if(pl>pr)return null;
        int k = m.get(preorder[pl]);
        int Lnum = k - il;
        //int Rnum = ir - k;
        TreeNode Node = new TreeNode(preorder[pl]);
        Node.left = dfs(preorder,inorder,pl + 1,pl + Lnum,il,il + Lnum);
        Node.right = dfs(preorder,inorder,pl +Lnum + 1,pr,il + Lnum + 1,ir);
        return Node;
    }
}