O(n) recursive solution without hashmap nor index


  • 0
    Z

    python solution:

    class Solution(object):
        def buildTree(self, inorder, postorder):
            """
            :type inorder: List[int]
            :type postorder: List[int]
            :rtype: TreeNode
            """
            def postdfs(stop):
                if postorder and inorder[-1] != stop:
                    root = TreeNode(postorder.pop())
                    root.right = postdfs(root.val)
                    inorder.pop()
                    root.left = postdfs(stop)
                    return root
            inorder, postorder = inorder[:], postorder[:]
            return postdfs(None)
    
    # 202 / 202 test cases passed.
    # Status: Accepted
    # Runtime: 62 ms
    # beats 97.20 %
    

    c++ solution:

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
            vector<int> in(inorder), post(postorder);
            return postdfs(in, post, (TreeNode *)NULL);
        }
    
        TreeNode * postdfs(vector<int> & in, vector<int> & post, TreeNode * stop) {
            if ( post.empty() || (stop && in.back() == stop->val) ) {
                return NULL;
            }
            TreeNode * root = new TreeNode(post.back());
            post.pop_back();
            root->right = postdfs(in, post, root);
            in.pop_back();
            root->left = postdfs(in, post, stop);
            return root;
        }
    };
    
    // 202 / 202 test cases passed.
    // Status: Accepted
    // Runtime: 9 ms
    // beats 91.06 %
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.