Fast runtime 10ms beats ~90% java recursion


  • 0
    E
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null){
                return null;
            }
            if(search(p, q) != null){
                return p;
            }
            if(search(q,p) != null){
                return q;
            }
            return lcaHelper(root, p, q);
          
        }
        private TreeNode lcaHelper(TreeNode root, TreeNode p, TreeNode q){
            if(search(root.left, p) != null && search(root.left, q)!= null){
                return lowestCommonAncestor(root.left, p, q);
            }    
            if(search(root.right, p) != null && search(root.right, q)!= null){
                return lowestCommonAncestor(root.right, p, q);
            }
            return root;
        }
        private TreeNode search(TreeNode node, TreeNode find){
            if(node == null){
                return null;
            }
            if(node == find){
                return node;
            }
            TreeNode nodeL = search(node.left, find);
            TreeNode nodeR = search(node.right, find);
            if(nodeL == null){
                return nodeR;
            }
            return nodeL;
            
        }
    

Log in to reply
 

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