目录

问题描述 

举例描述

实现

问题描述 

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]

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先（LCA）。

根据维基百科对LCA的定义：“最近公共祖先被定义为在节点p和节点q之间最近的节点，p和q都是他的后代（我们允许节点本身是节点的后代）。”

举例描述

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2

实现

           判断p，q和root之间的关系。如果p->val>q->val，那么root->val<q->val的话，就需要递归root->right。而如果root->val>p->vald的话，就需要递归root->left。如果不是这两种情况，那就说明root->val在[q->val,p->val]中，要么root是p和q的父母节点，要么root是p或q。无论如何，都可以返回root。以下是p>q的情况的流程图。

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {if(p->val<q->val){if(root->val<p->val)return lowestCommonAncestor(root->right,p,q);//重复else if(root->val>q->val)return lowestCommonAncestor(root->left,p,q);//重复elsereturn root;}else if(p->val>q->val){if(root->val<q->val)return lowestCommonAncestor(root->right,p,q);//重复else if(root->val>p->val)return lowestCommonAncestor(root->left,p,q);//重复elsereturn root;}elsereturn NULL;
}

以上代码有肉眼可见的重复，说明我们可以进一步优化。不论p和q的大小，如果root->val小于p和q的值，则说明需要递归root->right；如果root->val大于p和q的值，则说明需要递归root->left。

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {if (p->val<root->val && q->val<root->val)return lowestCommonAncestor(root->left,p,q);if (p->val>root->val && q->val>root->val)return lowestCommonAncestor(root->right,p,q);return root;}