二叉树中两个结点最近的父节点

在二叉树中，两个结点最近的公共祖先（Lowest Common Ancestor，LCA）是指在该二叉树上同时拥有这两个结点为后代的最深的结点，即深度最大的、同时是这两个结点祖先的结点。为了求出这个公共祖先，我们可以使用递归的方法，从根节点开始寻找。具体实现方法如下：
1. 如果根节点为空，返回空指针；
2. 如果根节点等于其中一个结点，返回该结点；
3. 在左子树中查找该结点，如果存在则返回左子树中该结点；
4. 在右子树中查找该结点，如果存在则返回右子树中该结点；
5. 如果左子树和右子树都能找到，则说明该结点为两个结点的最近公共祖先，返回根节点。

相关问题

求二叉树p所指结点的父结点

在二叉树结构中，如果给定一个指向某个节点p的指针，通常我们可以通过递归的方式来找到这个节点的父节点。对于非根节点，它的父节点会在其左孩子或右孩子的指针中保存。具体的步骤如下：

1. 如果p不是NULL（即它是一个有效的节点），那么它的`parent`通常是`p->left`或`p->right`，其中`left`表示左子节点，`right`表示右子节点，这取决于你想查找的是p的哪一侧的父节点。

2. 如果`p->left`或`p->right`也是非NULL，这意味着你需要进一步检查它们的父节点，直到找到NULL为止，因为NULL节点的父节点就是NULL。

如果使用迭代而非递归，可以设置两个指针，一个指向当前节点，另一个初始设置为NULL，然后遍历p的双亲链表（如果存在的话）。从`p`开始，如果`p->parent`不为NULL，则移动到`p->parent`；否则，`p`就是最底层的叶节点，此时`p->parent`就是NULL。

已知二叉树中的两个结点，求距离它们最近的共同祖先代码

在二叉树中找到两个节点的最近公共祖先（Lowest Common Ancestor，LCA）通常涉及递归遍历。这个问题可以使用“路径压缩”或“层序遍历”的思路解决。以下是使用Python的一个简单递归解法：

首先，假设每个节点都有一个parent指针，表示其直接父节点，以及一个isVisited标志，用于记录我们是否已经访问过这个节点。我们可以从两个目标节点开始，如果他们的父节点相同，那么当前节点就是最近公共祖先；如果不相同，我们将继续查找他们各自父节点的最近公共祖先。

class TreeNode:
    def __init__(self, val=0, left=None, right=None, parent=None):
        self.val = val
        self.left = left
        self.right = right
        self.parent = parent
        self.isVisited = False

def find_lca(root, p, q):
    if not root:
        return None
    
    root.isVisited = True
    if root == p or root == q:
        return root
    
    left_lca = find_lca(root.left, p, q)
    right_lca = find_lca(root.right, p, q)
    
    # 如果其中一个孩子是LCA，则当前节点也是LCA
    if left_lca and right_lca:
        return root
    # 否则，LCA位于未访问的子树中
    return left_lca if left_lca else right_lca

这里的关键在于利用了二叉搜索树的特性，当我们在一条路径上找不到LCA，就尝试另一条路径，直到找到为止。