Ac solution code

  • 0

    The basic idea is using recursion: check left child and right child of root, if both left child and right child are not null, then return root; else return left child or right child, which is not null.

    As the following:

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode a, TreeNode b) {
        if (root == null || root == a || root == b) 
            return root;// root is a or b
        TreeNode left = lowestCommonAncestor(root.left, a, b);// left branch includes a or b or both
        TreeNode right = lowestCommonAncestor(root.right, a, b);// right branch includes a or b or both
        if (left != null && right != null) 
            return root;// <--left and right is a or b, then its 'root' is the result (NOTE: left, right is not root's direct kids)
        return left != null ? left : right; // left or right includes both a and b

Log in to reply

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