LeetCode: 235. Lowest Common Ancestor of a Binary Search Tree

发表于 | 分类于

题目描述

Given a binary search tree (BST), find the lowest common ancestor (LCA) 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).”

Given binary search tree: root = [6,2,8,0,4,7,9,null,null,3,5]

img

Example 1:

1
2
3
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:

1
2
3
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.

在BST中找到两个点的共同ancestor。

由于是个BST，所以只需要根据节点值来判断，从头开始，最先出现在p和q之间的值的节点就是他们最开始的共同节点。如果说当前节点小于p和q，就检查当前节点的右子节点；反之检查当前节点的左子节点。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
private:
    TreeNode* findNode(TreeNode* root, int left, int right) {
        if (root->val == left || root->val == right)
            return root;
        if (root->val > left && root->val < right)
            return root;

        if (root->val > right)
            return findNode(root->left, left, right);
        else
            return findNode(root->right, left, right);

    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        int left = p->val;
        int right = q->val;

        if (left > right) {
            int tmp = left;
            left = right;
            right = tmp;
        }
        return findNode(root, left, right);
    }
};