Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Example 1:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.
Example 2:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
Example 3:
Input: root = [2,1], p = 2, q = 1
Output: 2
Constraints:
The number of nodes in the tree is in the range [2, 105].
-109 <= Node.val <= 109
All Node.val are unique.
p != q
p and q will exist in the BST.
Solutions
Solution 1
1 2 3 4 5 6 7 8 910111213141516171819
# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = NoneclassSolution:deflowestCommonAncestor(self,root:'TreeNode',p:'TreeNode',q:'TreeNode')->'TreeNode':while1:ifroot.val<min(p.val,q.val):root=root.rightelifroot.val>max(p.val,q.val):root=root.leftelse:returnroot
1 2 3 4 5 6 7 8 91011121314151617181920212223
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */classSolution{publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){while(true){if(root.val<Math.min(p.val,q.val)){root=root.right;}elseif(root.val>Math.max(p.val,q.val)){root=root.left;}else{returnroot;}}}}
1 2 3 4 5 6 7 8 9101112131415161718192021222324
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */classSolution{public:TreeNode*lowestCommonAncestor(TreeNode*root,TreeNode*p,TreeNode*q){while(1){if(root->val<min(p->val,q->val)){root=root->right;}elseif(root->val>max(p->val,q->val)){root=root->left;}else{returnroot;}}}};
1 2 3 4 5 6 7 8 91011121314151617181920
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funclowestCommonAncestor(root,p,q*TreeNode)*TreeNode{for{ifroot.Val<p.Val&&root.Val<q.Val{root=root.Right}elseifroot.Val>p.Val&&root.Val>q.Val{root=root.Left}else{returnroot}}}
# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = NoneclassSolution:deflowestCommonAncestor(self,root:'TreeNode',p:'TreeNode',q:'TreeNode')->'TreeNode':ifroot.val<min(p.val,q.val):returnself.lowestCommonAncestor(root.right,p,q)ifroot.val>max(p.val,q.val):returnself.lowestCommonAncestor(root.left,p,q)returnroot
1 2 3 4 5 6 7 8 9101112131415161718192021
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */classSolution{publicTreeNodelowestCommonAncestor(TreeNoderoot,TreeNodep,TreeNodeq){if(root.val<Math.min(p.val,q.val)){returnlowestCommonAncestor(root.right,p,q);}if(root.val>Math.max(p.val,q.val)){returnlowestCommonAncestor(root.left,p,q);}returnroot;}}
1 2 3 4 5 6 7 8 910111213141516171819202122
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */classSolution{public:TreeNode*lowestCommonAncestor(TreeNode*root,TreeNode*p,TreeNode*q){if(root->val<min(p->val,q->val)){returnlowestCommonAncestor(root->right,p,q);}if(root->val>max(p->val,q->val)){returnlowestCommonAncestor(root->left,p,q);}returnroot;}};
1 2 3 4 5 6 7 8 9101112131415161718
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funclowestCommonAncestor(root,p,q*TreeNode)*TreeNode{ifroot.Val<p.Val&&root.Val<q.Val{returnlowestCommonAncestor(root.Right,p,q)}ifroot.Val>p.Val&&root.Val>q.Val{returnlowestCommonAncestor(root.Left,p,q)}returnroot}