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 v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

_______6______ / \ ___2__ ___8__ / \ / \ 0 _4 7 9 / \ 3 5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

题目链接

题意：

给一个二叉搜索树，找到给定两个节点的最低的公共祖先节点。

这题首先应考虑二叉搜索树的性质，对于每一个节点，左子节点小于父节点，右子节点大于父节点，所以最低的公共祖先节点一定符合p和q分布在其左支和右支上的性质，通过判断p，q的val与root的val大小，判断p，q在root的哪边分支上，然后递归或循环，直到root满足左右分支分别有一个p或q为止。

代码如下：

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