从前序与中序遍历序列构造二叉树「变题」

105. 从前序与中序遍历序列构

private int[] preorder;
private Map<Integer, Integer> inorderMap = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
    this.preorder = preorder;
    for (int i = 0; i < inorder.length; i++) inorderMap.put(inorder[i], i);
    return f(0, preorder.length - 1, 0, inorder.length - 1);
}
private TreeNode f(int a, int b, int x, int y) {
    if (a > b || x > y) return null;
    int val = preorder[a];
    int i = inorderMap.get(val), left = i - x, right = y - i;
    TreeNode root = new TreeNode(val);
    root.left = f(a + 1, a + left, x, i - 1);
    root.right = f(a + left + 1, b, i + 1, y);
    return root;
}

变题一：迭代

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder == null || preorder.length == 0) return null;
    TreeNode root = new TreeNode(preorder[0]);
    Deque<TreeNode> st = new ArrayDeque<>();
    st.push(root);
    int idx = 0;
    for (int i = 1; i < preorder.length; i++) {
        int val = preorder[i];
        TreeNode node = st.peek();
        if (node.val != inorder[idx]) {
            node.left = new TreeNode(val);
            st.push(node.left);
        } else {
            while (!st.isEmpty() && st.peek().val == inorder[idx]) {
                node = st.poll();
                idx++;
            }
            node.right = new TreeNode(val);
            st.push(node.right);
        }
    }
    return root;
}

变题二：根据前序和中序输出后序

private int idx = 0;
private int[] preorder, postorder;
private Map<Integer, Integer> inorderMap = new HashMap<>();
public int[] buildTree(int[] preorder, int[] inorder) {
    this.preorder = preorder;
    postorder = new int[inorder.length];
    for (int i = 0; i < inorder.length; i++) inorderMap.put(inorder[i], i);
    f(0, preorder.length - 1, 0, inorder.length - 1);
    return postorder;
}
private void f(int a, int b, int x, int y) {
    if (a > b || x > y) return ;
    int val = preorder[a];
    int i = inorderMap.get(val), left = i - x, right = y - i;
    f(a + 1, a + left, x, i - 1);
    f(a + left + 1, b, i + 1, y);
    postorder[idx++] = val;
}

变题三：从中序与后序遍历序列构造二叉树

题目详情可见 从中序与后序遍历序列构造二叉树

private int[] postorder;
private Map<Integer, Integer> inorderMap = new HashMap<>();
public TreeNode buildTree(int[] inorder, int[] postorder) {
    this.postorder = postorder;
    for (int i = 0; i < inorder.length; i++) inorderMap.put(inorder[i], i);
    return f(0, postorder.length - 1, 0, inorder.length - 1);
}
private TreeNode f(int a, int b, int x, int y) {
    if (a > b || x > y) return null;
    int val = postorder[b];
    int i = inorderMap.get(val), left = i - x, right = y - i;
    TreeNode root = new TreeNode(val);
    root.left = f(a, a + left - 1, x, i - 1);
    root.right = f(a + left, b - 1, i + 1, y);
    return root;
}

变题四：变题三的迭代版本

public TreeNode buildTree(int[] inorder, int[] postorder) {
    if (postorder == null || postorder.length == 0) return null;
    TreeNode root = new TreeNode (postorder[postorder.length - 1]);
    Deque<TreeNode> st = new ArrayDeque<>();
    st.push(root);
    int idx = inorder.length - 1;
    for (int i = postorder.length - 2; i >= 0; i--) {
        int val = postorder[i];
        TreeNode node = st.peek();
        if (node.val != inorder[idx]) {
            node.right = new TreeNode(val);
            st.push(node.right);
        } else {
            while (!st.isEmpty() && st.peek().val == inorder[idx]) {
                node = st.poll();
                idx--;
            }
            node.left = new TreeNode(val);
            st.push(node.left);
        }
    }
    return root;
}