題目

給定一個二叉搜索樹, 找到該樹中兩個指定節點的最近公共祖先。
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結點 p、q，最近公共祖先表示為一個結點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先）。”
例如，給定如下二叉搜索樹: root = [6,2,8,0,4,7,9,null,null,3,5]

思考

對于普通二叉樹，利用回溯從底向上搜索，遇到一個結點的左子樹有p，右子樹有q，那么當前結點就是最近公共祖先。
對于有序樹，從上到下遍歷的時候，cur結點的數值在[p,q]區間，則說明該結點就是cur的最近公共祖先了。
確定返回值以及參數
參數：當前結點，兩個目標結點p，q
返回值：最近公共祖先，TreeNode*

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 

確定終止條件
遇到空結點就返回

if(cur == NULL) return cur;

確定單層邏輯
如果cur在區間左邊，那么說明區間在cur右子樹附近，遍歷右子樹。
如果cur在區間右邊，說明區間在cur左子樹附近，遍歷左子樹。
如果cur在區間中，則說明cur就是最近公共祖先。
注意，如果找到公共祖先，要返回這個結點。

//cur在區間右邊，所以需要在左子樹尋找if(cur->val > q->val && cur->val > p->val){TreeNode* left = traversal(cur->left,p,q);//說明找到了公共祖先，將這個結點返回if(left !=NULL) return left;}//cur在區間左邊，所以需要在右子樹尋找if(cur->val < q->val && cur->val < p->val){TreeNode* right = traversal(cur->right,p,q);//說明找到了公共祖先，將這個結點返回if(right !=NULL) return right;}//cur正好在區間中間，說明這個cur就是最近公共祖先，返回這個結點return cur;

AC代碼

/*** 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* traversal(TreeNode* cur, TreeNode* p, TreeNode* q){if(cur == NULL) return cur;//cur在區間右邊，所以需要在左子樹尋找if(cur->val > q->val && cur->val > p->val){TreeNode* left = traversal(cur->left,p,q);//說明找到了公共祖先，將這個結點返回if(left !=NULL) return left;}//cur在區間左邊，所以需要在右子樹尋找if(cur->val < q->val && cur->val < p->val){TreeNode* right = traversal(cur->right,p,q);//說明找到了公共祖先，將這個結點返回if(right !=NULL) return right;}//cur正好在區間中間，說明這個cur就是最近公共祖先，返回這個結點return cur;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {return traversal(root,p,q);}
};

迭代法

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