post order iterative solution using just set and stack, better than hashMap version with explanation


  • 1
    L

    using post order iterative way can help us record the parent path along iteration without HashMap.

    1. after find the first target node(p || q), put the current parent path from stack into set.
    2. after find the second target node, the stack has its parent path, just double break to get out of the double while loop.
    3. find the common ancester
    public class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            Stack<TreeNode> stack = new Stack();
            if(root == null) return null;
    
            TreeNode cur = root, prev = null;
            boolean foundOne = false;
            Set<TreeNode> set = new HashSet(); //for first found node's parent path
            while(!stack.isEmpty() || cur != null)
            {
                while(cur != null)
                {
                    stack.push(cur);
                    if((cur == p || cur == q) && !foundOne) //found first node
                    {
                        set.addAll(stack);
                        foundOne = true;
                    }
                    else if(cur == p || cur == q) break; //found second node, exit while loop
                    cur = cur.left;
                }
                if((cur == p || cur == q) && foundOne) break; //found second node, exit while loop
    
                cur = stack.peek();
                if(cur.right != null && prev != cur.right)
                {
                    cur = cur.right;
                }
                else
                {
                    prev = stack.pop();
                    cur = null;
                }
            }
    
    //if p is q's lca, p's path must be stored in the set first.
            while(!stack.isEmpty()) 
            {
                cur = stack.pop();
                if(set.contains(cur)) return cur;
            }
            return null; 
        }
    }
    

    }


Log in to reply
 

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