Pass most of the tests, but still got a bug. Can anyone help?


  • 0
    E

    I know there are much better solutions using recursion. But here I tried to solve it by getting all the paths for each target node, and then compare the paths to find the LCA. Most tests passed, but still not all. Can anyone help me find out where the bug is?

    public class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(p.val == q.val) //This case is undefined and boring.
                return root;
                
            List<Deque<TreeNode>> pPaths = getPath(root, p);
            List<Deque<TreeNode>> qPaths = getPath(root, q);
            
            int maxDepth = -1;
            TreeNode lca = null;
            for(Deque<TreeNode> pPathOrig: pPaths)
            {
                for(Deque<TreeNode> qPathOrig: qPaths)
                {
                    Deque<TreeNode> pPath = new ArrayDeque<TreeNode>(pPathOrig);
                    Deque<TreeNode> qPath = new ArrayDeque<TreeNode>(qPathOrig);
                    
                    int depth = -1;
                    TreeNode last = null;
                    while(!pPath.isEmpty() && !qPath.isEmpty())
                    {
                        TreeNode pLast = pPath.removeLast();
                        TreeNode qLast = qPath.removeLast();
                        if(pLast!=qLast)
                            break;
                        ++depth;
                        last = pLast;
                    }
                    
                    if(depth > maxDepth)
                    {
                        maxDepth = depth;
                        lca = last;
                    }
                }
            }
            return lca;
        }
        
        private List<Deque<TreeNode>> getPath(TreeNode root, TreeNode t)
        {
            //The path might not be unique, because numbers are not unique in the tree.
            List<Deque<TreeNode>> ret = new ArrayList<>();
            Deque<TreeNode> path = new ArrayDeque<TreeNode>();
            Deque<TreeNode> unprocessed = new ArrayDeque<TreeNode>();
            unprocessed.push(root);
            
            while(!unprocessed.isEmpty())
            {
                TreeNode current = unprocessed.pop();
                path.push(current);    
                if(current.val == t.val)
                {
                    ret.add(new ArrayDeque<TreeNode>(path));
                }
                
                if(current.right != null)
                    unprocessed.push(current.right);
                        
                if(current.left != null)
                    unprocessed.push(current.left);
                else
                    while(path.peek().right != unprocessed.peek())
                    {
                        path.pop();
                    }
            }
            return ret;
        }
    }

Log in to reply
 

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