Provide a more general way to handle such problem, not limit to BST


  • 0
    S

    While at begining i didn't notice it is a BST, which can be evaluate by its value. So i came up with this solution without using node's value.

    public class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null) return null;
            if ((p == root && isChild(root, q)) || 
                (q == root && isChild(root, p)) || 
                (isChild(root.left, p) && isChild(root.right, q)) || 
                (isChild(root.right, p) && isChild(root.left, q))) {
                return root;
            }
            TreeNode res = null;
            if((res = lowestCommonAncestor(root.left, p, q)) != null) return res;
            if((res = lowestCommonAncestor(root.right, p, q)) != null) return res;
            return null;
        }
    
        public boolean isChild(TreeNode root, TreeNode child) {
            if (root == child) return true;
            if (root == null) return false;
            return isChild(root.left, child) || isChild(root.right, child); 
        }
    }

  • 1
    T

    This solution runs in O(n^2) doesn't it?


Log in to reply
 

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