Construct Binary Tree from Inorder and Postorder Traversal

https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/

Given inorder and postorder traversal of a tree, construct the binary tree.

Thoughts

和上题思路一致，只是这次root是先从postorder的末尾找。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private TreeNode helper(int[] inorder, int instart, int inend, int[] postorder, int pstart, int pend) {
        if (instart > inend || pstart > pend) {
            return null;
        }
        int nodeVal = postorder[pend];
        int inpos = -1;
        // 0, 6 - 0
        for (int i = 0; i <= inend - instart; i++) {
            if (inorder[instart + i] == nodeVal) {
                inpos = i;
            }
        }
        TreeNode node = new TreeNode(inorder[instart + inpos]);
        node.left = helper(inorder, instart, instart + inpos - 1, postorder, pstart, pstart + inpos - 1);
        node.right = helper(inorder, instart + inpos + 1, inend, postorder, pstart + inpos, pend - 1);
        return node;
    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return helper(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }
}

Analysis

Errors:

1. inorder[instart + i] == nodeVal忘了写instart

   做题耗时: 15min

时间复杂度O(n^2).

Ver.2

和preorder-inorder同理, 只不过要倒过来处理. 从尾部遍历先建右树再建左树. 时间复杂度O(N).

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (postorder.length == 0) {
            return null;
        }

        Stack<TreeNode> stack = new Stack<>();        
        TreeNode root = new TreeNode(postorder[postorder.length - 1]), cur = root;
        for (int i = postorder.length - 2, j = inorder.length - 1; i >= 0; i--) {
            if (cur.val != inorder[j]) {
                cur.right = new TreeNode(postorder[i]);
                stack.push(cur);
                cur = cur.right;
            } else {
                j--;
                while (!stack.isEmpty() && stack.peek().val == inorder[j]) {
                    cur = stack.pop();
                    j--;
                }
                cur = cur.left = new TreeNode(postorder[i]);
            }
        }
        return root;
    }
}