Post-order Traversal solution with explanation


  • 0
    J

    I think of Stack at first glance, and then write this solution.
    My idea is that this problem ask to find a Lowest Common Parent node. With Stack and post-order traversal, we can keep the parent node in the Stack.

    Every time a node is visited (which means they will never get into the Stack), the code will check if it is a target node.

    • For the first found node, we use one node lcp to remember the parent of it.
    • If the current lcp is removed before we find the second target node, lcp will be replaced by its parent.

    p.s. there are in fact only 2 situation

    1. Target node p is a parent/ancestor of node q
    2. They are separately in left subtree and right subtree.
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    // Post-order traversal
    
    public class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            TreeNode lcp = null;
            Stack<TreeNode> stack = new Stack<TreeNode>();
            TreeNode cur = root, pre = null;
            int count = 0;
            while (cur != null || !stack.isEmpty()) {
                if (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                } else {
                    cur = stack.pop();
                    if (cur.right == null || cur.right == pre) {
                        if (cur == p || cur == q) {
                            count++;
                            if (count == 1) lcp = stack.peek(); // !stack.isEmpty(); 
                            if (count == 2) return lcp;
                        }
                        if (cur == lcp) lcp = stack.peek(); // !stack.isEmpty(); 
                        pre = cur;
                        cur = null;
                    } else {
                        stack.push(cur);
                        cur = cur.right;
                    }
                }
            }
            return lcp;
        }
    }
    

Log in to reply
 

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