题目描述
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
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 the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4] The order of output does not matter.
Example1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.
Example2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
NOTE
- All of the nodes’ values will be unique.
- p and q are different and both values will exist in the binary tree.
解题思路
- 递归使用
- Divide & Conquer 的思路
- 如果root为空，则返回空
- 如果root等于其中某个node，则返回root
- 如果上述两种情况都不满足，则divide，左右子树分别调用该方法
- Divide & Conquer中治这一步要考虑清楚，本题三种情况
- 如果left和right都有结果返回，说明此时的root是最小公共祖先
- 如果只有left有返回值，说明left的返回值是最小公共祖先
- 如果只有right有返回值，说明right的返回值是最小公共祖先
/**
* 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 || p == root || q == root){
return root;
}
TreeNode* left = lowestCommonAncestor(root -> left, p, q);
TreeNode* right = lowestCommonAncestor(root -> right, p, q);
if(left && right){
return root;
}
if(left){
return left;
}else{
return right;
}
return NULL;
}
};
