Comment trouver l'ancêtre commun le plus proche d'un arbre binaire en Java

Idée 1 : Supposons d'abord que cet arbre est un arbre de recherche binaire

Tout d'abord, ajoutons une explication supplémentaire de ce qu'est un arbre de recherche binaire :

Dans un arbre de recherche binaire, pour chaque nœud, son sous-arbre gauche Les valeurs ​​in sont tous plus petits que lui, et les valeurs du sous-arbre de droite sont toutes plus grandes que lui. Ainsi, le parcours dans l’ordre d’un arbre de recherche binaire est un ensemble ordonné de données.

Pour l'arbre ci-dessus, supposons que l'ancêtre commun le plus récent de p q est requis.

Ensuite, il y a les situations suivantes :

Pour les arbres binaires ordinaires, ce n'est rien de plus que ces situations : pq est à gauche, pq est à droite, pq est à gauche et un sur à droite, pq en a un est le nœud racine.

Alors récursivement, accédez au sous-arbre gauche et au sous-arbre droit pour trouver l'ancêtre commun du nœud p q s'il est trouvé, il renverra le nœud. S'il n'est pas trouvé, il reviendra vide.

Selon les idées ci-dessus, nous pouvons facilement écrire le code

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if(root == null) return null;

    // p 为当前树的根节点
    if(p == root) return p;
    // q 为当前树的根节点
    if(q == root) return q;
    
    // 去左子树中找
    TreeNode left = lowestCommonAncestor(root.left,p,q);
    // 去右子树中找
    TreeNode right = lowestCommonAncestor(root.right,p,q);

    // 左边右边都找到了
    if(left != null && right != null) {
        return root;
    }
    // 左边找到了，右边没找到
    if(left != null) {
        return left;
    }
    if(right != null) {
        return right;
    }
    return null;
}

Idée 2 : Supposons que l'arbre soit exprimé en représentation enfant-parent

Chaque nœud enregistrera l'adresse de son père nœud, vous pouvez effectuer une recherche en ligne couche par couche jusqu'à ce que vous trouviez le premier point d'intersection des deux listes chaînées, qui est leur ancêtre commun.

Pour les arbres binaires ordinaires, vous ne pouvez rechercher que vers le bas couche par couche, pas vers le haut, vous devez donc conserver les chemins des deux nœuds jusqu'au dernier nœud identique des deux chemins. Ici, nous utilisons une pile pour conserver les chemins de deux nœuds.

Insérez d'abord les éléments dans la pile avec plus d'éléments, puis assemblez les deux piles jusqu'à ce que les nœuds à extraire soient égaux, ce qui est leur ancêtre commun le plus proche.

Ensuite, la plus grande difficulté ici est le chemin de stockage.

Une pile est utilisée pour stocker le chemin ici. Lorsqu'un nœud est traversé, le nœud est mis dans la pile, puis les arbres gauche et droit du nœud sont recherchés de manière récursive. Si le chemin est trouvé, le chemin est conservé. , et s'il n'est pas trouvé, il est sauté.

Supposons que vous recherchiez p dans l'image ci-dessous :

Placez d'abord le nœud racine dans la pile, recherchez récursivement dans le sous-arbre gauche du nœud racine, s'il n'est pas trouvé, faites-le apparaître et recherchez à droite sous-arbre.

Lorsque la racine atteint 6, on constate que les côtés gauche et droit du nœud sont vides, indiquant que le nœud cible n'est pas trouvé dans le sous-arbre 6 apparaît et continue la recherche dans le sous-arbre droit de 5. .

De même, il est introuvable dans le sous-arbre droit de 5. Il apparaîtra jusqu'à ce qu'il recherche le sous-arbre droit de 3. Lorsqu'il arrive à 1, il est trouvé.

// 用于找节点的路径
public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
    if(root == null || node == null) {
        return false;
    }
    // 将当前节点放入栈中
    stack.push(root);
    
    if(root.val == node.val) {
        return true;// 找到了
    }
    // 当前节点没找到，去左子树找
    boolean flag = getPath(root.left,node,stack);
    // 左子树中找到了，直接返回
    if(flag) {
        return true;
    }
    // 左子树没找到，去右子树找
    flag = getPath(root.right,node,stack);
    // 右子树中找到了，直接返回
    if(flag) {
        return true;
    }
    
    // 左右子树都没找到，弹出节点
    stack.pop();
    return false;

}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if(root == null) {
        return null;
    }
    Stack<TreeNode> stackp = new Stack<>();
    Stack<TreeNode> stackq = new Stack<>();

    // 分别得到  p q 的路径
    getPath(root,p,stackp);
    getPath(root,q,stackq);

    int sizep = stackp.size();
    int sizeq = stackq.size();

    if(sizep > sizeq) {
        int size = sizep - sizeq;
        // 弹出元素直至两栈中元素个数相等
        while(size > 0) {
            stackp.pop();
            size--;
        }
    }else {
        int size = sizeq - sizep;
        // 弹出元素直至两栈中元素个数相等
        while(size > 0) {
            stackq.pop();
            size--;
        }
    }

    // 一起弹出，直到找到第一个相同的元素
    while(!stackp.isEmpty() && !stackq.isEmpty()) {
        if(stackp.peek() == stackq.peek()) {
        	// 找到了，就返回该节点
            return stackq.pop();
        }else {
            stackp.pop();
            stackq.pop();
        }
    }
    // 没找到，返回 null
    return null;
}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!