題目描述
給定一個二叉樹, 找到該樹中兩個指定節(jié)點的最近公共祖先。
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結(jié)點 p各薇、q项贺，最近公共祖先表示為一個結(jié)點 x，滿足 x 是 p峭判、q 的祖先且 x 的深度盡可能大（一個節(jié)點也可以是它自己的祖先）开缎。”
例如林螃，給定如下二叉樹: root = [3,5,1,6,2,0,8,null,null,7,4]
_______3______
/ \
___5__ ___1__
/ \ / \
6 _2 0 8
/ \
7 4
示例 1:
輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
輸出: 3
解釋: 節(jié)點 5 和節(jié)點 1 的最近公共祖先是節(jié)點 3奕删。
示例 2:
輸入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
輸出: 5
解釋: 節(jié)點 5 和節(jié)點 4 的最近公共祖先是節(jié)點 5。因為根據(jù)定義最近公共祖先節(jié)點可以為節(jié)點本身疗认。
說明:
所有節(jié)點的值都是唯一的完残。
p伏钠、q 為不同節(jié)點且均存在于給定的二叉樹中。
分析
通過返回值是否為NULL來標識是否找到相應(yīng)的節(jié)點
p,q在左右子樹谨设，當前的根節(jié)點就是公共的祖先節(jié)點
如果p,q同在左子樹或者右子樹熟掂，公共的祖先節(jié)點是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) {
if(root == NULL || root == p || q == root){
return root;
}
auto l = lowestCommonAncestor(root->left, p, q);
auto r = lowestCommonAncestor(root->right, p, q);
if(l != NULL && r != NULL) {
return root;
}
return l != NULL ? l : r;
}
};
題目鏈接
https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/description/
