Java easy solution!


  • 0
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null || p == null || q == null) {
                return null;
            }
            
            ArrayList<TreeNode> nodes = new ArrayList<>();
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                TreeNode curNode = queue.poll();
                nodes.add(curNode);
                
                if (curNode.left != null) {
                    queue.offer(curNode.left);
                }
                if (curNode.right != null) {
                    queue.offer(curNode.right);
                }
            }
            
            HashSet<TreeNode> pset = new HashSet<>();
            HashSet<TreeNode> qset = new HashSet<>();
            for (int i = nodes.size() - 1; i >= 0; --i) {
                TreeNode curNode = nodes.get(i);
                
                if (curNode == p || pset.contains(curNode.left) || pset.contains(curNode.right)) {
                    pset.add(curNode);
                    pset.remove(curNode.left);
                    pset.remove(curNode.right);
                }
                if (curNode == q || qset.contains(curNode.left) || qset.contains(curNode.right)) {
                    qset.add(curNode);
                    qset.remove(curNode.left);
                    qset.remove(curNode.right);
                }
                
                if (pset.contains(curNode) && qset.contains(curNode)) {
                    return curNode;
                }
            }
            
            return null;
        }
    

Log in to reply
 

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