Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Recursive solution
- //Time: O(n), 13ms
- //Space: O(h)
- class Solution {
- public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
- if(root == null) return null;//Base case 1: Not found
- if(root == p) return p;//Base Case 2: Found one
- if(root == q) return q;
- TreeNode left = lowestCommonAncestor(root.left, p, q);
- TreeNode right = lowestCommonAncestor(root.right, p, q);
- if(left != null && right != null) {//Case 1, p and q are in different branch of root
- return root;
- }
- if(left == null) {//Case 2, p and q are both in right subtree OR Case 4, p and q are not decedents of the root
- return right;
- } else {//Case 3, p and q are both in left subtree
- return left;
- }
- }
- }
- /**
- * Definition for a binary tree node.
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
Add Comment
Please, Sign In to add comment