235. Lowest Common Ancestor of a Binary Search Tree

解題思路

這題的目標，是找出兩個節點 p, q 的共同且 lowest 的祖先節點。又因為是 BST，所以一個節點的左子樹肯定都比它數值小、右子樹則會比較大。

觀察範例，會發現只要找到值介於 p, q 間的 node 就好。

程式碼

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(p->val > q->val)
            swap(p, q);
        while(true)
        {
            if(p->val <= root->val && root->val <= q->val)
                return root;
            if(root->val > q->val)
                root = root->left;
            else
                root = root->right;
        }
    }
};