求二叉树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。

相关问题

求二叉树中两个结点的最低公共祖先结点

在二叉树中，最低公共祖先（LCA）指的是两个结点的公共祖先中离这两个结点最近的那个结点。求二叉树中两个结点的最低公共祖先可以通过递归实现。

首先，从二叉树的根节点开始，如果根节点为空或者等于其中的一个结点，那么直接返回根节点。否则，分别递归左右子树，找到两个结点在左右子树中的位置。

如果两个结点都在左子树中，那么继续在左子树中递归查找。如果两个结点都在右子树中，那么继续在右子树中递归查找。如果两个结点一个在左子树一个在右子树，那么当前的根节点就是它们的最低公共祖先，直接返回。

下面是求二叉树中两个结点的最低公共祖先的示例代码：

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` 的最低公共祖先结点。

求二叉树中求结点总数和二叉树叶子结点的代码

下面是二叉树求结点总数和叶子结点数量的代码实现（假设二叉树的节点结构体为Node）：

求结点总数：

int countNodes(Node* root) {
    if (root == nullptr) {
        return 0;
    }
    return countNodes(root->left) + countNodes(root->right) + 1;
}

求叶子结点数量：

int countLeaves(Node* root) {
    if (root == nullptr) {
        return 0;
    }
    if (root->left == nullptr && root->right == nullptr) {
        return 1;
    }
    return countLeaves(root->left) + countLeaves(root->right);
}

注意，这里的叶子结点指的是没有左右子节点的节点。如果定义叶子结点为没有任何儿子节点的节点，则需要修改判断条件。