问题1.二叉搜索树的最近公共祖先

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

思路

求二叉搜索树中的两个节点p，q的最近公共祖先的思路比较简单： ①如果遍历到的节点node的值在p节点的值和q节点的值之间，则说明p，q分别在node的左右子树之中，则node就是p和q的最近公共祖先。 ②如果node的值大于p和q的值，则p和q应该都在node 的左子树中，即此时递归查找node的左子树。 ③如果node的值小于p和q的值，则p和q应该都在node的右子树中，则此时递归查找node的右子树。

代码

/** * 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==NULL) return NULL; int val = root->val; if((val>=p->val&&val<=q->val)||(val>=q->val&&val<=p->val)) return root; else if(val>p->val&&val>q->val) return lowestCommonAncestor(root->left, p, q); else return lowestCommonAncestor(root->right, p, q); } };

问题2.二叉树的最近公共祖先

剑指 Offer 68 - II. 二叉树的最近公共祖先

思路

参考https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/solution/mian-shi-ti-68-ii-er-cha-shu-de-zui-jin-gong-gon-7/

代码

/** * 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==NULL || root == p || root == q) return root; TreeNode* le = lowestCommonAncestor(root->left, p, q); TreeNode* ri = lowestCommonAncestor(root->right, p, q); if(le==NULL) return ri; if(ri==NULL) return le; return root; } };