My comprehension of O(n) solution from @hongzhi


  • 32
    L

    Below is the O(n) solution from @hongzhi but that discuss is closed now 'cause @hongzhi says little about his code.

    https://oj.leetcode.com/discuss/6334/here-is-my-o-n-solution-is-it-neat

    I've modified some of and tried this code and got AC.
    Just share about some comprehension about his code.

    I've modified vtn(vector) to stn(stack) in that stack is probably what this algs means and needs.

    What matters most is the meaning of stn.

    Only nodes whoes left side hasn't been handled will be pushed into stn.

    And inorder is organized as (inorder of left) root (inorder of right),

    And postorder is as (postorder of left) (postorder of right) root.

    So at the very begin, we only have root in stn and we check if inorder.back() == root->val and in most cases it's false(see Note 1). Then we make this node root's right sub-node and push it into stn.

    Note 1: this is actually (inorder of right).back() == (postorder of right).back(), so if only there's no right subtree or the answer will always be false.

    Note 2: we delete one node from postorder as we push one into stn.

    Now we have [root, root's right] as stn and we check inorder.back() == stn.top()->val again.

    • true means inorder.back() is the root node and needs handled left case.
    • false means inorder.back() is the next right sub-node

    So when we encounter a true, we will cache stn.top() as p and delete both nodes from inorder and stn.

    Then we check inorder.size(), if there's no nodes left, it means p has no left node.

    Else the next node in inorder could be p's left node or p's father which equals to the now stn.top() (remember we popped p from stn above).

    If the latter happens, it means p has no left node and we need to move on to p's father(stn.top()).

    If the former happens, it means p has one left node and it's postorder.back(), so we put it to p's left and delete it from the postorder and push the left node into stn 'cause it should be the next check node as the postorder is organized as above.

    That's all of it. The algs just build a binary tree. :)

    Inform me if there's anything vague or wrong, I'm open to any suggestions.

    class Solution {
    public:
        TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
            if(inorder.size() == 0)return NULL;
            TreeNode *p;
            TreeNode *root;
            stack<TreeNode *> stn;
            
            root = new TreeNode(postorder.back()); 
            stn.push(root); 
            postorder.pop_back(); 
            
            while(true)
            {
                if(inorder.back() == stn.top()->val) 
                {
                    p = stn.top();
                    stn.pop(); 
                    inorder.pop_back(); 
                    if(inorder.size() == 0) break;
                    if(stn.size() && inorder.back() == stn.top()->val)
                        continue;
                    p->left = new TreeNode(postorder.back()); 
                    postorder.pop_back();
                    stn.push(p->left);
                }
                else 
                {
                    p = new TreeNode(postorder.back());
                    postorder.pop_back();
                    stn.top()->right = p; 
                    stn.push(p); 
                }
            }
            return root;
        }
    };

  • 1

    Thanks and +1 for your detailed explanation.


  • 7
    M

    Thank you for sharing your explanation.

    Here's a Java version of this solution:

    import java.util.Stack;
    
    public class Solution {
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            if (inorder == null || inorder.length < 1) return null;
            int i = inorder.length - 1;
            int p = i;
            TreeNode node;
            TreeNode root = new TreeNode(postorder[postorder.length - 1]);
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            p--;
            
            while (true) {
                if (inorder[i] == stack.peek().val) { // inorder[i] is on top of stack, pop stack to get its parent to get to left side
                    if (--i < 0) break;
                    node = stack.pop();
                    if (!stack.isEmpty() && inorder[i] == stack.peek().val) {// continue pop stack to get to left side
                        continue;
                    }
                    node.left = new TreeNode(postorder[p]);
                    stack.push(node.left);
                } else { // inorder[i] is not on top of stack, postorder[p] must be right child
                    node = new TreeNode(postorder[p]);
                    stack.peek().right = node;
                    stack.push(node);
                }
                p--;
            }
            
            return root;
        }
    }

  • 0
    L

    Thank you for your detailed explanation!

    And here is the python version:

    class Solution:
        # @param inorder, a list of integers
        # @param postorder, a list of integers
        # @return a tree node
        def buildTree(self, inorder, postorder):
            if len(inorder) == 0:
                return None
            root = TreeNode(postorder.pop())
            stn = list()
            stn.append(root)
            
            while True:
                if inorder[-1] == stn[-1].val:
                    p = stn.pop()
                    inorder.pop()
                    if len(inorder) == 0: break
                    if len(stn) != 0 and inorder[-1] == stn[-1].val: continue
                    p.left = TreeNode(postorder.pop())
                    stn.append(p.left)
                else:
                    p = TreeNode(postorder.pop())
                    stn[-1].right = p
                    stn.append(p)
            
            return root

  • 0
    B

    Still too hard to understand. The logic is very unusual.

    Serialization of the recursive version could actually suffice what you said, i guess. So no mystery. Work out the recursive version first. then use stack to do it iteratively


  • 1
    A

    Thanks for your idea! I think your code will change the input parameters postorder and inorder, so I just changed it a little bit by using two integers to record the indexes of current elements in postorder and inorder. Now this code will not change the input parameters at all.

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    	if (inorder.size() == 0 || postorder.size() == 0)
    		return 0;
    	TreeNode* root = new TreeNode(postorder.back());
    	if (postorder.size() == 1)
    		return root;
    
    	stack<TreeNode*> st;
    	st.push(root);
    	int i = postorder.size() - 2;
    	int j = inorder.size() - 1;
    	TreeNode* node;
    	while (true)
    	{
    		if (st.top()->val == inorder[j])
    		{
    			node = st.top();
    			st.pop();
    			j--;
    			if (j < 0)
    				break;
    			if (!st.empty() && st.top()->val == inorder[j])
    				continue;
    			node->left = new TreeNode(postorder[i]);
    			i--;
    			st.push(node->left);
    		}
    		else
    		{
    			node = new TreeNode(postorder[i]);
    			i--;
    			st.top()->right = node;
    			st.push(node);
    		}
    	}
    	return root;
    }

  • 0
    C
    This post is deleted!

  • 0
    C

    Take a look at this explanation for pre and in case, similar thought but clearer explanation.
    https://leetcode.com/discuss/2297/the-iterative-solution-is-easier-than-you-think


  • 0
    M

    clear rewrite, i do learn something. just FYI, Stack is deprecated somehow, you can use Deque instead.


  • 0
    M

    go through the code several times, really cool :p upvoted


  • 0

    Great solutions! Thanks for sharing.

    I thought the explanation is still a bit difficult to understand so I wrote a simpler one with comments and high-level understanding of this approach. It uses index so does not modify original parameters.

    https://discuss.leetcode.com/topic/54223/annotated-iterative-solution-with-comments-does-not-modify-parameters

    Hope it helps.


Log in to reply
 

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