[ leetcode ] 235. Lowest Common Ancestor of a Binary Search Tree

Binary Search Tree가 주어졌을 때, 서로 다른 두 노드의 가장 낮은 level의 공통 조상을 찾는 문제입니다.

(Lowest Common Ancestor)

BST의 특성을 잘 이해하여 한 노드의 값보다 크면 오른쪽 자식, 작으면 왼쪽 자식에 존재한다는 개념을 이용합니다.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

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