根据先序遍历和中序遍历建立二叉树

问题

​ 已知一棵二叉树的先序遍历以及中序遍历，重建二叉树。二叉树的每一个节点有三个属性，左子节点，右子节点，以及节点值。

思路

先序遍历服从规则“根左右”，所以由此可知，对于一个先序遍历得到的数组，第一个元素一定是根节点；

中序遍历服从规则”左根右“，所以由此可知，对于一个中序遍历得到的数组，根节点左边的元素都属于根节点的左子树，而根节点右边的元素都属于根节点的右子树；

所以，我们可以先通过先序遍历的第一个元素确定根节点，然后通过中序遍历结合根节点，获得当前根节点的左右子树，再将子树看成一棵独立的树，继续使用先序遍历判断根节点，中序遍历判断子树的方式，最终建立起整棵树；

例子

假设有一棵二叉树，先序遍历为{1,2,4,7,3,5,6,8}，中序遍历为{4,7,2,1,5,3,8,6}，则建树过程如下：

至此，二叉树便重建完成；

代码

树的节点

public class TreeNode {
    int val;        //当前节点的值
    TreeNode left;  //左子节点
    TreeNode right; //右子节点

    TreeNode(int x) {
        val = x;
    }
}

建树方法

/**
* pre：线序遍历得到的数组
* in：中序遍历得到的数组
*/
public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
    if(pre.length == 0) {
        return null;
    }

    int root = pre[0];
    TreeNode node = new TreeNode(root);

    //寻找根节点在in中的索引
    int i = 0;
    for( ; i<in.length; ++i) {
        if(in[i] == root) {
            break;
        }
    }

    //建立左子树
    int[] leftIn = Arrays.copyOfRange(in, 0, i);
    int[] leftPre = Arrays.copyOfRange(pre, 1, i+1);
    node.left = reConstructBinaryTree(leftPre, leftIn);

    //建立右子树
    int[] rightIn = Arrays.copyOfRange(in, i+1, in.length);
    int[] rightPre = Arrays.copyOfRange(pre, i+1, pre.length);
    node.right = reConstructBinaryTree(rightPre, rightIn);

    return node;
}

建树代码（优化）

public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
    return getRootTreeNode(pre, 0, pre.length-1, in, 0, in.length-1);
}

/**
* preL：当前子树在先序遍历的数组中的起始下标
* preR：当前子树在先序遍历的数组中的结束下标
* inL：当前子树在中序遍历的数组中的起始下标
* inR：当前子树在中序遍历的数组中的起始下标
*/
public TreeNode getRootTreeNode(int[] pre, int preL,
                                int preR, int[] in, int inL, int inR) {
    if(preL > preR) {
        return null;
    }

    TreeNode node = new TreeNode(pre[preL]);

    for(int i=inL; i<=inR; ++i) {
        if(in[i] == pre[preL]) {

            node.left = getRootTreeNode(pre, preL+1, preL+i-inL, in, inL, i-1);
            node.right = getRootTreeNode(pre, preL+i-inL+1, preR, in, i+1, inR);
            break;
        }
    }

    return node;
}