[数据结构与算法]二叉树的最近公共祖先

二叉树的最近公共祖先

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

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

分析：递归三部曲。有返回值时，子节点的返回值如何界定

#include "_myPrint.cpp"
#include "stack"
#include "queue"
using namespace std;

// 找最近公共祖先
class Solution{
public:
    // 递归三步 1。参数和返回类型 2。终止条件 3。每一层需要处理的逻辑
    // 这里输入两个节点找祖先 TreeNode* xx(TreeNode* p, TreeNode* q, TreeNode* root)
    // 搜索 节点碰到空或者q和p时候 终止搜索
    // 一般来说 搜索一条边（局部）就直接返回的写法
    // if (left) return;   if (right) return;
    // 而如果需要搜索整个树，父亲节点需要 接收、传递 两个子节点的返回值，那么先接住子节点的返回值
    // if (left) l = left; if (right) r = right; return deal(l & r);
    TreeNode* searchCommonAcent(TreeNode* root, TreeNode* q, TreeNode* p){
        // 终止条件（单节点处理逻辑）   如果找到空节点了 返回空 如果找到其中之一节点 返回这个节点
        if (!root || root == q || root == p) return root;
        TreeNode* left = searchCommonAcent(root -> left, q, p);
        TreeNode* right = searchCommonAcent(root -> right, q, p);
        // 对每一层递归 需要处理左右节点的返回值
        if (left && right) return root;
        else if (!left) return right;
        else if (!right) return left;
        else return NULL;
    }



};

int main(){
    Solution s;
    TreeNode* root = new TreeNode(8);
    TreeNode* l = new TreeNode(7);
    TreeNode* r = new TreeNode(9);
    TreeNode* lr = new TreeNode(7);
    TreeNode* rl = new TreeNode(8);
    root->left = l;
    root->right = r;
    l->right = lr;
    r->left=rl;
    TreeNode* res =  s.searchCommonAcent(root, lr, rl);
    cout << res -> val << endl;

}