Deep Understanding on the Iterative Solution


  • 4
    W

    Here I provide my understanding on how the iterative solution work.

    • Let's first observe the sequence of inorder traversal.
      1) ####$---##$---0+++
      2) 0: The root node of a tree
      3) #: the left child or grandchildren of root node 0, without right child
      4) $: the left child or grandchildren of root node 0, with a right child or subtree.
      5) --- : represent right subtree of node $
      6) +++: represent right subtree of root node.

    • Let's observe the sequence of preorder traveral
      1) 0$##$###------+++
      2) The symbols are the same.

    • Maintain two pointers: ptrin, ptrpre
      1) ptrpre: pointer to preorder sequence, always points to the next node that is about to be created.
      2) ptrin: pointer to inorder sequence. When we keep pushing into stack, ptrin always points to the deepest left child of a subtree. When we keeping popping out nodes, ptrin points to nodes that has no right child, until it points to the root of the right subtree of a node that is just popped out from the stack.

    • Maintain a stack
      1) Similar with the stack in inorder traversal, it always stores the chain of left children in a subtree.
      2) When pushing stack, we are traversing the chain of left children in a subtree, and we keeping creating new node and make it as the left child of the node at stack top.
      3) When poping stack, we always pop out a node that has no right child, until we find a node that has right child (subtree).

    • Maintain a temp pointer, that always points to a node popped from stack, the last node that is popped out from the stack has right child (subtree). So the newly created node will be the right child of temp.

    • Procedures of my algorithm:
      1) Create the root node of the entire tree, record the root node for the purpose of return. Push the root node into the stack.
      2) While we has remaining node to create

    (a) When we enter a new iteration, ptrin always points to the deepest left grandchild of a tree. So as long as we have not reached it, we can safely keep creating new left child (grandchild) for top node at stack. This actually creating the chain of left children for a tree, namely ###$#$0. The newly-created node will be pushed in the stack. So, next created node will be its left child.

    (b) Now, after the previous step, we have reached the deepest left child of a tree. Remember inorder traveral, now we need to retreat from the deepest left child until we find the first node that has a right child or subtree. We use a temp pointer to record the node that has right child, than we create the right child for it. This is achievable, because ptrpre always points to the next node that will be created. In other word, now, the node pointed by ptrpre is the right child. This invariant is ensured by the characteristics of preorder traversal. Remember the symbol presentation: 0$##$###------+++. After we create the left children chain: 0$##$###, now the ptrpre points to the first -, which is the right child of the first node with right child (the second $).
    (c) Repeat step (a) and step (c) until we create all nodes.

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
            if(preorder.empty()) return NULL;
            int ppre = 0, pin = 0;
            TreeNode* root = new TreeNode(preorder[ppre++]);
            stack<TreeNode*> stk;
            stk.push(root);
            while(true) {
                while(stk.top()->val != inorder[pin]) {
                    TreeNode* newnode = new TreeNode(preorder[ppre++]);
                    stk.top()->left = newnode;
                    stk.push(newnode);
                }
                TreeNode* node;
                while(!stk.empty() && stk.top()->val == inorder[pin]) {
                    node = stk.top();
                    stk.pop();
                    pin++;
                }
                if(ppre == preorder.size()) break;
                TreeNode* newnode = new TreeNode(preorder[ppre++]);
                node->right = newnode;
                stk.push(newnode);
            }
            return root;
        }
    

Log in to reply
 

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