Java iterative solution with 1 stack


  • 2
    D

    The idea is when finding p or q the first time current stack must contain LCA. So when stack size is decreased the pop node could be the LCA if another node (p or q) is found under it.

    public class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null|| root == p || root == q) return root;
    
            TreeNode n = root;
            TreeNode res = null;
            int size = -1;
            Stack<TreeNode> s = new Stack<TreeNode>();
            while (n!=null || !s.empty()) {
                while (n!=null) {
                    s.push(n);
                    if (n == p || n == q) {
                        if (res == null) { //find p or q the first time
                            res = n;
                            size = s.size();
                        } else return res; //find both p and q
                    }
                    n = n.left;
                }
                n = s.pop();
                if (s.size() < size) {
                    size = s.size();
                    res = n;
                }
                n = n.right;
            }
            return res;
        }
    }
    

  • 0
    Q

    what a brilliant solution!


Log in to reply
 

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