Java DFS solution


  • 6
    C
    public class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null) return null;
            List<TreeNode> pathTop = new ArrayList<>();
            List<TreeNode> pathToq = new ArrayList<>();
            if (!pathToNode(pathTop, root, p) || !pathToNode(pathToq,root,q)) return null;
            int min = Math.min(pathTop.size(), pathToq.size());
            int pointer = min;
            for (int i = 0; i < min; i++) {
                if (pathTop.get(i).val != pathToq.get(i).val) {
                    pointer = i;
                    break;
                }
            }
            return pathTop.get(pointer - 1);  
        }
        
        public boolean pathToNode(List<TreeNode> path, TreeNode root, TreeNode n) {
            if (root == null) return false;
            path.add(root);
            if (root == n) {// use root == n instead of root.val == n.val
                return true;
            }
            if (pathToNode(path, root.left, n)) return true;
            if (pathToNode(path, root.right, n)) return true;
            path.remove(path.size() - 1);
            return false;
        }
    }

Log in to reply
 

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