二叉树共同祖先如何保证一个结点不是另一个结点祖先
时间: 2024-05-28 14:12:59 浏览: 30
为了保证一个结点不是另一个结点的祖先,我们需要在查找共同祖先的过程中,判断这两个结点是否在同一个子树中。如果在同一个子树中,那么其中一个结点必然是另一个结点的祖先。因此,我们需要在遍历二叉树的过程中,记录每个节点的父节点信息。
一种常用的方法是使用哈希表,将每个节点的指针和其对应的父节点指针存储起来。在查找共同祖先的过程中,我们可以先分别记录两个节点的路径,然后从根节点开始比较这两个路径,直到找到最后一个相同的节点,这个节点就是它们的最近公共祖先。
另一种方法是使用递归。在递归遍历二叉树的过程中,我们可以先判断当前节点是否是其中一个结点,如果是,就返回该节点。如果不是,我们就递归遍历该节点的左子树和右子树,分别查找这两个结点。如果左右子树都能找到这两个结点,那么当前节点就是它们的最近公共祖先。如果只能在左子树或右子树中找到其中一个结点,那么继续向上返回该节点,继续在更高层的递归中查找另一个结点,直到找到最近公共祖先为止。
相关问题
求二叉树中两个结点的最低公共祖先结点
在二叉树中,最低公共祖先(LCA)指的是两个结点的公共祖先中离这两个结点最近的那个结点。求二叉树中两个结点的最低公共祖先可以通过递归实现。
首先,从二叉树的根节点开始,如果根节点为空或者等于其中的一个结点,那么直接返回根节点。否则,分别递归左右子树,找到两个结点在左右子树中的位置。
如果两个结点都在左子树中,那么继续在左子树中递归查找。如果两个结点都在右子树中,那么继续在右子树中递归查找。如果两个结点一个在左子树一个在右子树,那么当前的根节点就是它们的最低公共祖先,直接返回。
下面是求二叉树中两个结点的最低公共祖先的示例代码:
```python
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
if not root or root == p or root == q:
return root
left = lowestCommonAncestor(root.left, p, q)
right = lowestCommonAncestor(root.right, p, q)
if left and right:
return root
return left or right
```
这里的 `TreeNode` 是二叉树的结点类,`lowestCommonAncestor` 函数接受三个参数:根节点 `root`,要查找的两个结点 `p` 和 `q`,函数返回 `p` 和 `q` 的最低公共祖先结点。
C++求二叉树中两个结点的最低公共祖先结点
求二叉树中两个结点的最低公共祖先结点可以采用递归的方式实现,具体步骤如下:
1. 如果当前节点为空,则返回空。
2. 如果当前节点为其中一个目标节点,则返回该节点。
3. 递归查找左子树并返回结果。
4. 递归查找右子树并返回结果。
5. 如果左右子树都找到了目标节点,则当前节点为最低公共祖先结点。
下面是一个示例代码实现:
```
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
if (!root) return NULL;
if (root == p || root == q) return root;
struct TreeNode* left = lowestCommonAncestor(root->left, p, q);
struct TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left && right) return root;
return left ? left : right;
}
```
在上面的代码中,输入参数 `root` 为二叉树的根节点,`p` 和 `q` 分别为两个目标节点,函数返回最低公共祖先结点。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)