力扣：236.二叉树的最近公共祖先(C++)

本文主要是介绍力扣：236.二叉树的最近公共祖先(C++)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

1. 题目描述
2. 题目解析
- 2.1 思路一
- 2.1 思路二

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
题目来源: 力扣…二叉树的最近公共祖先

1. 题目描述

百度百科中最近公共祖先的定义为：“对于有根树 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 。因为根据定义最近公共祖先节点可以为节点本身。

提示：

树中节点数目在范围 [2, 105] 内。
-10^9 <= Node.val <= 10^9
所有 Node.val 互不相同。
p != q
p 和 q 均存在于给定的二叉树中。

2. 题目解析

2.1 思路一

判断p q是否分别在当前节点左右子树中或者其中一个就是树的根。
我们可以通过递归来实现这个过程。具体思想是：

如果当前节点是其中一个目标节点，则直接返回当前节点。
如果在当前节点的左右子树中分别找到目标节点，说明当前节点就是最近公共祖先。
否则 p q都在当前节点的左子树或者右子树中，因此在左子树和右子树中继续递归查找。

代码如下：

//判断节点x是否在树中
bool InTree(TreeNode* root, TreeNode* x)
{if (root == nullptr) return false;if (root == x) return true;return InTree(root->left, x) || InTree(root->right, x);
}
reeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
{//当前节点是其中一个目标节点，则直接返回当前节点if (root == p || root == q) return root;//去当前左子树中查找p节点bool pInLeft = InTree(root->left, p);//在左子树中就不在右子树，因此对pInLeft取反，就是其是否在右子树中的情况bool pInRight = !pInLeft;//对q节点和对p节点一样bool qInLeft = InTree(root->left, q);bool qInRight = !qInLeft;//在当前节点的左右子树中分别找到目标节点，说明当前节点就是最近公共祖先if ((pInLeft && qInRight) || (qInLeft && pInRight)){return root;} else if (pInLeft && qInLeft){//p q都在当前节点的左子树中，因此在左子树中继续递归查找return lowestCommonAncestor(root->left, p, q);} else {//p q都在当前节点的右子树中，因此在右子树中继续递归查找return lowestCommonAncestor(root->right, p, q);}
}

2.1 思路二

通过找到从根节点到目标节点的路径，然后将其转换成链表相交问题。
这种方法的步骤如下：

找到根节点到p节点的路径。
找到根节点到q节点的路径。
找到这两条路径的最后一个公共节点。

画个图理解一下：

在这里插入图片描述
代码如下：

//找根节点到节点x的路径bool GetPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& st){if (root == nullptr) return false;st.push(root);if (root == x) return true;if (GetPath(root->left, x, st)){return true;}if (GetPath(root->right, x, st)){return true;}st.pop();return false;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {stack<TreeNode*> pPath, qPath;GetPath(root, p, pPath);//找到根节点到p节点的路径。GetPath(root, q, qPath);//找到根节点到q节点的路径。//路径长的先走，直到路径一样长while (pPath.size() != qPath.size()){if (pPath.size() > qPath.size()){pPath.pop();}else{qPath.pop();}}//找这两条路径的最后一个公共节点while (pPath.top() != qPath.top()){pPath.pop();qPath.pop();}return pPath.top();}