236. 二叉树的最近公共祖先

题目描述

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

解题思路

class Solution {
public:
TreeNode*pp;
TreeNode*res=0;
TreeNode*qq;
int f(TreeNode*r){
    if(!r)return 0;
    int left=f(r->left);int right=f(r->right);
    int a=r==pp||r==qq?1:0;
    a+=left+right;
    if(!res&&a==2){res=r;}return a;
}
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        pp=p;qq=q;
        f(root);
        return res;
    }
};

f表示在子树中找到的个数，找到2个的时候就设置res就行了

学习感想