https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/
要点是后序遍历,这样就可以从树底开始搜索,寻找最近公共祖先
class Solution {
public:
// 返回的是最近公共祖先,若返回null则说明没有
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);
// 左右子树都有对应节点,意味着此时root节点为最近公共祖先
if(left && right)return root;
// 右有左没有,此时right被递归赋值了,就是最近公共祖先
if(left==nullptr)return right;
// 左有右没有,此时left被递归赋值了,就是最近公共祖先
return left;
}
};
标签:right,TreeNode,祖先,二叉树,公共,236,root,leetcode,left
From: https://www.cnblogs.com/lxl-233/p/18181098