题解 | #重建二叉树#

题目(Java题解)

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

示例

input:
    preOrder:    [1,2,3,4,5,6,7]
    inOrder:    [3,2,4,1,6,5,7]
output:    
    {1,2,5,3,4,6,7}

解题思路

首先明确二叉树遍历的特点，前序遍历结果中，第一个节点为当前树的根节点，其后分别为左子树和右子树，中序遍历结果中，根节点位于数组中，左子树在根节点左侧，右子树在根节点右侧，那么如果基于这两个数组构建二叉树的话，在构建当前子数的时候，只需要找到当前树的根节点以及左子树的根节点并连接和右子树的根节点并连接。方法返回的为当前子数的根节点，即对每一棵子数的操作都是找到根节点然后连接左右子树并返回，如果左右子树没有节点则返回null。

1. 当前，前序遍历数组为[1,2,3,4,5,6,7],中序遍历数组为[3,2,4,1,6,5,7]，可以得到根节点的值为1，左子树节点为process(preOrder2,inOrder2);右子树节点为process(preOrder3,inOrder3)，需要准确跟踪数组区间的变化，将变化的部分写入到方法的参数中便于跟踪。
2. 依次递归调用直到叶子节点，叶子节点当前两个数组中都仅有一个元素，左右子树都返回空。
   如果此时面试官问你当前方法在时间复杂度上还能不能优化，那么无外乎就是再问你能否通过空间换时间的方法来提升效率，这里可以通过map来提前存储关于inOrder中数组索引与数组值的对应关系，这样就不需要每次递归都要进行一次遍历循环。
   时间复杂度：
   基于访问的时间复杂度O(N)

实例代码

Recursion

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre == null || pre.length == 0){
            return null;
        }
        TreeNode root = processRecursion(pre,in);
        return root;
    }
    public TreeNode processRecursion(int [] pre,int [] in){
        int preEnd = pre.length - 1;
        int inEnd = in.length - 1;
        return recursion(pre,0,preEnd,in,0,inEnd);
    }
    public TreeNode recursion(int [] pre,int preStart,int preEnd,
                              int [] in,int inStart,int inEnd){
        if(preStart > preEnd){
            return null;
        }
        if(preStart == preEnd){
            return new TreeNode(pre[preStart]);
        }
        TreeNode currRoot = new TreeNode(pre[preStart]);
        int index = 0;
        for(int i = inStart; i <= inEnd; i++){
            if(in[i] == currRoot.val){
                index = i;
                break;
            }
        }
        currRoot.left = recursion(pre,preStart + 1,preStart + index - inStart,
                                 in,inStart,index - 1);
        currRoot.right = recursion(pre,preStart + index - inStart + 1,preEnd,
                                  in,index + 1,inEnd);
        return currRoot;
    }
}

Recursion+HashMap

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre == null || pre.length == 0){
            return null;
        }
        TreeNode root = processRecursionHashMap(pre,in);
        return root;
    }
    public TreeNode processRecursionHashMap(int [] pre,int [] in){
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < in.length; i++){
            map.put(in[i],i);
        }
        int preEnd = pre.length - 1;
        int inEnd = in.length - 1;
        return recursion(map,pre,0,preEnd,in,0,inEnd);
    }
    public TreeNode recursion(Map<Integer,Integer> map,int [] pre,int preStart,int preEnd,
                              int [] in,int inStart,int inEnd){
        if(preStart > preEnd){
            return null;
        }
        if(preStart == preEnd){
            return new TreeNode(pre[preStart]);
        }
        TreeNode currRoot = new TreeNode(pre[preStart]);
        int index = map.get(currRoot.val);
        currRoot.left = recursion(map,pre,preStart + 1,preStart + index - inStart,
                                 in,inStart,index - 1);
        currRoot.right = recursion(map,pre,preStart + index - inStart + 1,preEnd,
                                  in,index + 1,inEnd);
        return currRoot;
    }
}