根据前序、中序遍历重构二叉树

定义节点类型

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

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

重构二叉树

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

    public TreeNode reConstructBinaryTree(int[] pre, int startPre, int endPre,
            int[] in, int startIn, int endIn) {

        if (startPre > endPre || startIn > endIn)
            return null;

        TreeNode root = new TreeNode(pre[startPre]);// 构造树根
        for (int i = startIn; i <= endIn; i++) {
            // 中序遍历中找树根
            if (in[i] == pre[startPre]) {

                root.left = reConstructBinaryTree(pre, startPre + 1, i
                        - startIn + startPre, in, startIn, i - 1);
                root.right = reConstructBinaryTree(pre, i - startIn + startPre
                        + 1, endPre, in, i + 1, endIn);
                break;
            }
        }

        return root;
    }
}

测试

public class Test {
    public static void main(String[] args) {
        new ReconstructBinaryTree().reConstructBinaryTree(new int[] { 1, 2, 4,
                7, 3, 5, 6, 8 }, new int[] { 4, 7, 2, 1, 5, 3, 8, 6 });
    }
}

分析

前序遍历：12473568
中序遍历：47215386

重构过程：

1. 前序遍历中的第一个值为树根
2. 树根在中序遍历中的位置，左侧为左子树的中序遍历结果（472），右侧为右子树的中序遍历结果（5386）
3. 在前序遍历中，左子树的前序遍历结果为（247），右子树的前序遍历结果为（3568）
4. 则2为左子树的树根，3为右子树的树根
5. 重复上述操作直至结束