和235题类似，236的答案可以放在235里AC，但235是二叉搜索树，可以利用该特性优化代码实现。
/**
* 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 *left = lowestCommonAncestor(root->left,p,q);
TreeNode *right = lowestCommonAncestor(root->right,p,q);
if(NULL == left)
return right;
else if(NULL == right)
return left;
else
return root;
//one line judge
//return left == NULL ? right:right == NULL ? left:root;
}
};运行结果:
Runtime: 16 ms, faster than 94.88% of C++ online submissions for Lowest Common Ancestor of a Binary Tree.
Memory Usage: 14.8 MB, less than 5.21% of C++ online submissions for Lowest Common Ancestor of a Binary Tree.
2021.05.25笔记
更好理解的代码如下：
/**
* 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 == nullptr || root == p || root ==q) return root;
TreeNode * left = lowestCommonAncestor(root->left,p,q);
TreeNode * right = lowestCommonAncestor(root->right,p,q);
if(left == nullptr && right == nullptr)
return nullptr;
if(left != nullptr && right != nullptr)
return root;
return (left == nullptr) ? right:left;
}
};