描述

给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。

思路1：递归+分治

• 前序遍历：根左右
• 中序遍历：左根右

1. 前序遍历第一个元素为根节点，即1
2. 在中序遍历序列中找到对应的元素1
3. 此时左半部分为左子树{4,7,2}，对应的前序遍历序列为{2,4,7}。
4. 右半部分为右子树{5,3,8,6}，对应的前序遍历序列为{3,5,6,8}。
5. 用同样的方法找到左子树的根节点为2，右子树的根节点为3。分别作为1的子节点{1,2,3}
6. 不断分解，直到子树长度为0

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        int len = pre.length;
        if(len == 0) {
            return null;
        }
        TreeNode root = new TreeNode(pre[0]);
        for(int i = 0; i < len; i++) {
            if(root.val == vin[i]) {
                //左半部分
                int[] leftPre = Arrays.copyOfRange(pre, 1, i + 1);
                int[] leftVin = Arrays.copyOfRange(vin, 0, i);
                root.left = reConstructBinaryTree(leftPre, leftVin);
                //右半部分
                int[] rightPre = Arrays.copyOfRange(pre, i + 1, len);
                int[] rightVin = Arrays.copyOfRange(vin, i + 1, len);
                root.right = reConstructBinaryTree(rightPre, rightVin);
                break;
            }
        }
        return root;
    }
}

思路2：使用栈

前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}

遍历前序序列，下一个节点要么是左节点，要么是右节点或者其祖先的右节点

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        int len = pre.length;
        if(len == 0) {
            return null;
        }
        TreeNode ret = new TreeNode(pre[0]);
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = ret;
        int j = 0;
        for(int i = 1; i < len; i++) {
            if(cur.val != vin[j]) {
                // 到达最左端
                cur.left = new TreeNode(pre[i]);
                stack.push(cur);
                cur = cur.left;
            } else {
                j++;
                // 找到合适的祖先
                while(!stack.isEmpty() && stack.peek().val == vin[j]) {
                    cur = stack.pop();
                    j++;
                }
                cur.right = new TreeNode(pre[i]);
                cur = cur.right;
            }
        }
        return ret;
    }
}