二叉树共同祖先如何保证一个结点不是另一个结点祖先

为了保证一个结点不是另一个结点的祖先，我们需要在查找共同祖先的过程中，判断这两个结点是否在同一个子树中。如果在同一个子树中，那么其中一个结点必然是另一个结点的祖先。因此，我们需要在遍历二叉树的过程中，记录每个节点的父节点信息。

一种常用的方法是使用哈希表，将每个节点的指针和其对应的父节点指针存储起来。在查找共同祖先的过程中，我们可以先分别记录两个节点的路径，然后从根节点开始比较这两个路径，直到找到最后一个相同的节点，这个节点就是它们的最近公共祖先。

另一种方法是使用递归。在递归遍历二叉树的过程中，我们可以先判断当前节点是否是其中一个结点，如果是，就返回该节点。如果不是，我们就递归遍历该节点的左子树和右子树，分别查找这两个结点。如果左右子树都能找到这两个结点，那么当前节点就是它们的最近公共祖先。如果只能在左子树或右子树中找到其中一个结点，那么继续向上返回该节点，继续在更高层的递归中查找另一个结点，直到找到最近公共祖先为止。

相关问题

c语言二叉树共同祖先

以下是两种C语言实现二叉树共同祖先的方法：

方法一：

typedef struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

// 查找p或q结点是否在以root为根的二叉树中
bool findNode(BiTree root, BiTNode *p) {
    if (root == NULL) {
        return false;
    }
    if (root == p) {
        return true;
    }
    if (findNode(root->lchild, p) || findNode(root->rchild, p)) {
        return true;
    }
    return false;
}

// 查找p和q的最近公共祖先
BiTNode *nearest_ancestor(BiTree root, BiTNode *p, BiTNode *q) {
    if (root == NULL || p == NULL || q == NULL) {
        return NULL;
    }
    if (!findNode(root, p) || !findNode(root, q)) {
        return NULL;
    }
    if (root == p || root == q) {
        return root;
    }
    BiTNode *left = nearest_ancestor(root->lchild, p, q);
    BiTNode *right = nearest_ancestor(root->rchild, p, q);
    if (left != NULL && right != NULL) {
        return root;
    } else if (left != NULL) {
        return left;
    } else {
        return right;
    }
}

方法二：

typedef struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

typedef struct {
    BiTNode *elem[100];
    int top;
} Stack;

// 初始化栈
void init_stack(Stack *s) {
    s->top = -1;
}

// 入栈
void push(Stack *s, BiTNode *node) {
    s->top++;
    s->elem[s->top] = node;
}

// 出栈
void pop(Stack *s) {
    s->top--;
}

// 获取栈顶元素
BiTNode *get_top(Stack *s) {
    return s->elem[s->top];
}

// 查找从根结点到指定结点的路径
bool path(BiTree root, BiTNode *node, Stack *s) {
    if (root == NULL) {
        return false;
    }
    push(s, root);
    if (root == node) {
        return true;
    }
    if (path(root->lchild, node, s) || path(root->rchild, node, s)) {
        return true;
    }
    pop(s);
    return false;
}

// 查找p和q的最近公共祖先
BiTNode *nearest_ancestor(BiTree root, BiTNode *p, BiTNode *q) {
    Stack s1, s2;
    BiTNode *Node1;
    init_stack(&s1);
    init_stack(&s2);
    path(root, p, &s1);
    path(root, q, &s2);
    Node1 = get_top(&s1);
    if (get_top(&s1) != get_top(&s2)) {
        return NULL;
    }
    for (int i = 1; i < s1.top && i < s2.top; i++) {
        if (s1.elem[i] != s2.elem[i]) {
            return Node1;
        }
        Node1 = s1.elem[i];
    }
    return Node1;
}

Java声明三叉链表表示的二叉树类,实现二叉树的基本操作以及以下操做:构造一颗三叉链表表示的二叉树。 返回指定结点的父母结点。 返回指定结点的所有祖先结点。 返回两结点最近的共同祖先结点,给出代码并详细注释

好的，以下是 Java 声明三叉链表表示的二叉树类，并实现二叉树的基本操作以及给出相关操作代码和注释：

public class BinaryTree {
    
    // 二叉树结点类
    private static class BinaryTreeNode {
        int data; // 结点数据
        BinaryTreeNode left; // 左子结点
        BinaryTreeNode right; // 右子结点
        BinaryTreeNode parent; // 父结点
        
        public BinaryTreeNode(int data) {
            this.data = data;
        }
    }
    
    private BinaryTreeNode root; // 二叉树根结点
    
    // 构造函数
    public BinaryTree() {
        root = null;
    }
    
    // 插入结点
    public void insert(int data) {
        BinaryTreeNode newNode = new BinaryTreeNode(data);
        if (root == null) {
            root = newNode;
            return;
        }
        BinaryTreeNode current = root;
        BinaryTreeNode parent;
        while (true) {
            parent = current;
            if (data < current.data) {
                current = current.left;
                if (current == null) {
                    parent.left = newNode;
                    newNode.parent = parent;
                    return;
                }
            } else {
                current = current.right;
                if (current == null) {
                    parent.right = newNode;
                    newNode.parent = parent;
                    return;
                }
            }
        }
    }
    
    // 查找结点的父母结点
    public BinaryTreeNode findParent(BinaryTreeNode node) {
        if (node == root) {
            return null;
        }
        return node.parent;
    }
    
    // 查找结点的所有祖先结点
    public void findAncestors(BinaryTreeNode node) {
        if (node == null) {
            return;
        }
        System.out.print(node.data + " ");
        findAncestors(node.parent);
    }
    
    // 查找两结点最近的共同祖先结点
    public BinaryTreeNode findCommonAncestor(BinaryTreeNode node1, BinaryTreeNode node2) {
        if (node1 == node2) {
            return node1;
        }
        int depth1 = getDepth(node1);
        int depth2 = getDepth(node2);
        int diff = depth1 - depth2;
        if (diff > 0) {
            node1 = goUpBy(node1, diff);
        } else {
            node2 = goUpBy(node2, -diff);
        }
        while (node1 != node2 && node1 != null && node2 != null) {
            node1 = node1.parent;
            node2 = node2.parent;
        }
        return (node1 == null || node2 == null) ? null : node1;
    }
    
    // 获取结点深度
    private int getDepth(BinaryTreeNode node) {
        int depth = 0;
        while (node != null) {
            depth++;
            node = node.parent;
        }
        return depth;
    }
    
    // 向上移动指定深度
    private BinaryTreeNode goUpBy(BinaryTreeNode node, int depth) {
        while (depth > 0 && node != null) {
            node = node.parent;
            depth--;
        }
        return node;
    }
}

以上是 Java 声明三叉链表表示的二叉树类，并实现了插入结点、查找结点的父母结点、查找结点的所有祖先结点、查找两结点最近的共同祖先结点等操作。具体使用时，可以根据需要进行调用。