• 前序遍历为{根节点,{左孩子树},{右孩子树}},中序遍历为{{左孩子树},根节点,{右孩子树}}
  • 可以从前序遍历拿出根节点(首位)确定中序遍历数组的根节点位置,从而划分左右子树在两序遍历数组的范围,接下来就是左右子树的构建过程,即将一个大问题分割成了相同类型但规模更小的子问题,直接递归解决。
public class Solution {
    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        return reConstructBinaryTreeRec(pre, 0, pre.length - 1, in, 0, in.length - 1);
    }

    public TreeNode reConstructBinaryTreeRec(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd) {
        // 处理数组为空判断
        if(preStart > preEnd || inStart > inEnd) {
            return null;
        }

        // 找出根节点
        int rootPosition = inStart - 1;
        while(++rootPosition <= inEnd) {
            if(pre[preStart] == in[rootPosition]) {
                break;
            }
        }

        // 建立根节点并给构建左右孩子节点
        TreeNode root = new TreeNode(pre[preStart]);
        root.left = reConstructBinaryTreeRec(pre, preStart + 1, preStart + rootPosition - inStart, in, inStart, rootPosition - 1);
        root.right = reConstructBinaryTreeRec(pre, preStart + rootPosition - inStart + 1, preEnd, in, rootPosition + 1, inEnd);
        return root;
    }
}