8ms java. Not the most elegant algo out there but


  • 1
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null) return root;
            
            Deque<TreeNode> path = new ArrayDeque<TreeNode>();
            
            // find the path, or all the ancestors, from root to one of the nodes, in this case, p
            TreeNode temp = root;
            while(temp != null && temp.val != p.val) {
                if(p.val < temp.val) {
                    path.add(temp);
                    temp = temp.left;
                } else {
                    path.add(temp);
                    temp = temp.right;
                }
            }
            // adding itself to path in case of p is ancestor of q itself
            path.add(p);
            
            // backtrack the path to find the ancestor for q.
            // Since the path contains all p's ancestors, so once we find q's ancestor it is the common ancestor of p and q.
            // Since it's backtracking, so it is the LCA
            while(!path.isEmpty()) {
                temp = path.removeLast();
                if(isAncestor(temp, q)) return temp;
            }
            
            return root;
        }
        
        public boolean isAncestor(TreeNode temp, TreeNode q) {
            while(temp != null) {
                if(q.val == temp.val) return true;
                else if(q.val < temp.val) temp = temp.left;
                else temp = temp.right;
            }
            return false;
        }
    }
    

Log in to reply
 

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