[LeetCode] Lowest Common Ancestor of a Binary Search Tree

更新时间：2022-06-09 19:26:56

Well, remember to take advantage of the property of binary search trees, which is, node -> left -> val < node -> val < node -> right -> val. Moreover, both p and q will be the descendants of the root of the subtree that contains both of them. And the root with the largest depth is just the lowest common ancestor. This idea can be turned into the following simple recursive code.

 1 class Solution {
 2 public:
 3     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
 4         if (p -> val < root -> val && q -> val < root -> val)
 5             return lowestCommonAncestor(root -> left, p, q);
 6         if (p -> val > root -> val && q -> val > root -> val)
 7             return lowestCommonAncestor(root -> right, p, q);
 8         return root;
 9     }
10 };

Of course, we may also solve it iteratively.

 1 class Solution {
 2 public:
 3     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
 4         TreeNode* cur = root;
 5         while (true) {
 6             if (p -> val < cur -> val && q -> val < cur -> val)
 7                 cur = cur -> left;
 8             else if (p -> val > cur -> val && q -> val > cur -> val)
 9                 cur = cur -> right;
10             else return cur;
11         }
12     }
13 };

上一篇 : ：[LeetCode] Max Points on a Line下一篇 : [LeetCode] Palindrome Linked List

[LeetCode] Lowest Common Ancestor of a Binary Search Tree

相关阅读

推荐文章