Leetcode：236. 二叉树的最近公共祖先（C++）

目录

问题描述

实现代码与解析

原理思路:

---

问题描述

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

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

示例 1

输入root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出3
解释节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2

输入root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出5
解释节点 5 和节点 4 的最近公共祖先是节点 5 。
因为根据定义最近公共祖先节点可以为节点本身。

示例 3

输入root = [1,2], p = 1, q = 2
输出1

实现代码与解析

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
    {
        if(root==NULL) return NULL;
        if(root==p) return p;
        if(root==q) return q;
        TreeNode* left=lowestCommonAncestor(root->left,p,q);
        TreeNode* right=lowestCommonAncestor(root->right,p,q);
        //找到公共祖先返回
        if(left==p&&right==q||left==q&&right==p) return root;
        //已经找到祖先就返回祖先,只找到一个结点返回其此结点两个结点都未找到返回NULL
        return left?left:right;    
    }   
};

原理思路:

        比较简单啊就直接写解题过程了这里用的是递归。

        1、首先确定终止条件很明显当我们遇到了NULL或者pq这两个结点就返回。

if(root==NULL) return NULL;
if(root==p) return p;
if(root==q) return q;

        2、然后就是递归逻辑很明显这题需要左右子树的返回信息所以用后序遍历来处理。

TreeNode* left=lowestCommonAncestor(root->left,p,q);
TreeNode* right=lowestCommonAncestor(root->right,p,q);
.........
//后序处理代码

        3、之后就是后序的处理代码了当该结点的左子树返回了q结点右子树返回了p结点或者左右换一下顺序左子树返回了p结点右子树返回了q结点我们就返回该根结点。

//找到公共祖先返回
if(left==p&&right==q||left==q&&right==p) return root;

        4、最后这步是重点了虽然代码简单但是其很精妙处理了很多种情况先把代码放出来然后再给出解答。

return left?left:right;

第一种情况

        qp当前均未找到时这行代码会返回NULL符合逻辑。

第二种情况

        qp当前只找到了一个时这行代码返回非空的也就当前找到的那个符合逻辑。

第三种情况

        qp的祖先已经找到了当前结点的左右子树有一颗返回了祖先有一颗返回了NULL这行代码返回非空的也就是祖先符合逻辑。

第四种情况

        q为p子树的某个结点或p为q子树的某个结点这时q或p自己就为其祖先由终止条件可知此情况下遇到祖先就返回了祖先的根节点就符合第三种情况返回了祖先符合逻辑。

        所以别看这行代码短但是却为这题的关键所在大家在写题时也要把所有情况都考虑到思考如何用最简单的代码来表达出来。