C# Fastest Solution


  • 0
    K

    The base case is when the node we are checking is null, p, or q. In the case that it is p or q, we need to return that node up the recursive stack, until we get to the call that the other subtree contained the opposite of p or q. The moment we find this, this is the LCA, which we propagate back up again. If the node is null, we reached a dead end and simply collapse the recursive stack until we converge with a meaningful stack frame.

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     public int val;
     *     public TreeNode left;
     *     public TreeNode right;
     *     public TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null || root == p || root == q){
                return root;
            }
            TreeNode left = LowestCommonAncestor(root.left, p, q);
            TreeNode right = LowestCommonAncestor(root.right, p, q);
            
            if(left != null && right != null){
                return root;
            }
            
            return left == null ? right : left;
        }
    }
    

Log in to reply
 

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