描述

image.png

示例 1：

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2：

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 输出: 2 解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

题解

这道题的具体解法，可参看 这篇文章

  1. /**
  2.  * C++
  3.  * Definition for a binary tree node.
  4.  * struct TreeNode {
  5.  *     int val;
  6.  *     TreeNode *left;
  7.  *     TreeNode *right;
  8.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  9.  * };
  10.  */
  11. class Solution {
  12. public:
  13.     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
  14.         // 其实并不需要这个终止条件，因为题目中说了p、q 为不同节点且均存在于给定的二叉搜索树中。也就是说一定会找到公共祖先的，所以并不存在遇到空的情况。
  15.         // if(root === nullptr) return root 
  17.         // p,q 异侧
  18.         if((root->val - p->val) * (root->val - q->val) <= 0)  return root;
  20.         // p和q位于root的同侧
  21.         return lowestCommonAncestor(root->val > p->val ? root->left : root->right, p, q);
  22.     }
  23. };