DFS Java solution


  • 6
    Q

    First find treepath for p. Next find treepath for q. Finally compare tree pathes for common ancestor.

    public class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            List<TreeNode> pAns = new ArrayList<TreeNode>();
            List<TreeNode> qAns = new ArrayList<TreeNode>();
            findAncestors(p, root, pAns);
            findAncestors(q, root, qAns);
    
            TreeNode anc = root;
            int i = 1;
            while (i<pAns.size() && i<qAns.size()){
                if (pAns.get(i) == qAns.get(i)){
                    anc = pAns.get(i);
                }
                else{
                    break;
                }
                i++;
            }
            return anc;
        }
        
        private boolean findAncestors(TreeNode toFind, TreeNode parent, List<TreeNode> ans){
            if (parent == null){
                return false;
            }
            if (toFind == parent){
                ans.add(parent);
                return true;
            }
            ans.add(parent);
            if (findAncestors(toFind,parent.left,ans)){
                return true;
            }
            if (findAncestors(toFind,parent.right,ans)){
                return true;
            }
            ans.remove(ans.size()-1);
            return false;
        }
    }

  • 0
    S

    Though, if use ArrayList in the arg list instead of List, there is StackOverflow Error during runtime; there is a limit on the depth of tree if recursion is used and one test case almost reached that limit.


  • 0
    L

    I had the same problem and it went right after changing ArrayList to List. Could u explain a little more what happened in this process? I suppose whichever type it is, it will always create a reference in the stack pointing to the arrayList in the heap. How can stack overflow?


  • 0
    F

    This one can be used for both LCA and LCP, and also very easy to understand. like it!


Log in to reply
 

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