C++ Clear API


  • 0
    S

    In-order traverse ==> left root right
    Post-order traverse ==> left right root
    Reverse-post-order traverse ==> root right left

    We will build the tree recursively using reverse-post-order traverse.

    Example:
    vector<int> inorder = {4, 8, 2, 5, 1, 6, 3, 7}
    vector<int> postorder = {8, 4, 5, 2, 6, 7, 3, 1}
    The sequence of nodes that we are going to build is
    '1' -> '3' -> '7' -> '6' -> '2' -> '5' -> '4' ->'8', we can use a "nextNode" index to denote the node that we are going to build. Therefore, we don't need to pass the post-order index API.

    class Solution {
    private: int nextNode;
    public:
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
            nextNode = postorder.size()-1;
            return rootRL(inorder, postorder, 0, inorder.size()-1);
    
        }
        //Reverse-post-order to build tree => root Right Left
        TreeNode* rootRL(vector<int>& inorder, vector<int>& postorder, int inStart, int inEnd){
            if(inStart>inEnd) return NULL;
    
            TreeNode * root = new TreeNode(postorder[nextNode--]);//update next node
    
            if(inStart==inEnd) return root;
    
            int idx = searchRoot(inorder, inStart, inEnd, root->val);
    
            root->right =rootRL(inorder, postorder, idx+1, inEnd);//second part of inorder array
            root->left = rootRL(inorder, postorder, inStart, idx-1);//first part of inorder array
    
            return root;
        }
    
        int searchRoot(vector<int>& inorder,int inStart, int inEnd, int target){
            for(int i=inStart;i<=inEnd; i++){//Must exist.
                if(inorder[i]==target) return i;
            }
        }
    
    };
    

Log in to reply
 

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