Comment obtenir l'ancêtre commun le plus proche des arbres binaires et des arbres de recherche binaires en PHP

Étant donné un arbre de recherche binaire, trouvez l'ancêtre commun le plus proche de deux nœuds spécifiés dans l'arbre. La définition de l'ancêtre commun le plus proche dans l'Encyclopédie Baidu est la suivante : "Pour deux nœuds p et q d'un arbre enraciné T, l'ancêtre commun le plus proche est représenté par un nœud x, tel que x est l'ancêtre de p et q et la profondeur de x est aussi grand que possible.

La définition de l'ancêtre commun le plus proche dans l'Encyclopédie Baidu est la suivante : "Pour deux nœuds p et q d'un arbre enraciné T, l'ancêtre commun le plus proche est représenté par un nœud x, tel que x est l'ancêtre de p et q et la profondeur de x est Peut être grand (un nœud peut aussi être son propre ancêtre) "

Par exemple, étant donné l'arbre de recherche binaire suivant : root = [6,2,8,0,4,7,9,null,null, 3, 5]

Exemple 1 :

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

Exemple 2 :

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

Idées de résolution de problèmes

Cette question vous demande de trouver l'ancêtre commun le plus proche d'un arbre de recherche binaire, et la caractéristique de un arbre de recherche binaire est l'enfant de gauche. Tous les nœuds de l'arbre sont plus petits que le nœud actuel, tous les nœuds du sous-arbre droit sont plus grands que le nœud actuel et chaque sous-arbre a les caractéristiques ci-dessus, ce problème est donc facile à résoudre. traversant à partir du nœud mis à jour

Si les valeurs des deux nœuds sont toutes deux inférieures au nœud racine, cela signifie qu'elles sont toutes les deux sur le sous-arbre gauche du nœud racine, nous regardons vers le sous-arbre gauche si les valeurs. des deux nœuds sont supérieurs au nœud racine, cela signifie qu'ils sont tous les deux sur le sous-arbre droit du nœud racine, nous regardons vers le sous-arbre droit si la valeur d'un nœud est supérieure au nœud racine et que la valeur d'un nœud est. inférieur au nœud racine, cela signifie que l'un d'eux est sur le sous-arbre gauche du nœud racine et l'autre sur le sous-arbre droit du nœud racine, alors le nœud racine est leur nœud ancêtre commun le plus proche.

Code

/** 
* Definition for a binary tree node. 
* class TreeNode { 
    * public $val = null; 
    * public $left = null; 
    * public $right = null; 
    * function __construct($value) { 
        $this->val = $value; 
     } 
     * } 
*/
     class Solution {
    /** 
    * @param TreeNode $root 
    * @param TreeNode $p 
    * @param TreeNode $q 
    * @return TreeNode 
    */
    function lowestCommonAncestor($root, $p, $q) {
        //如果根节点和p,q的差相乘是正数，说明这两个差值要么都是正数要么都是负数，也就是说
        //他们肯定都位于根节点的同一侧，就继续往下找
        while (($root->val - $p->val) * ($root->val - $q->val) > 0)
            $root = $p->val < $root->val ? $root->left : $root->right;
        //如果相乘的结果是负数，说明p和q位于根节点的两侧，如果等于0，说明至少有一个就是根节点
        return $root;
    }}

Le moins ancêtre commun de l'arbre binaire

Étant donné un arbre binaire, trouvez l'ancêtre commun le plus proche des deux nœuds spécifiés dans l'arbre.

La définition de l'ancêtre commun le plus proche dans l'Encyclopédie Baidu est la suivante : "Pour deux nœuds p et q d'un arbre enraciné T, l'ancêtre commun le plus proche est représenté par un nœud x, tel que x est l'ancêtre de p et q et la profondeur de x est Peut être grand (un nœud peut aussi être son propre ancêtre) »

Par exemple, étant donné l'arbre binaire suivant : root = [3,5,1,6,2,0,8,null,null,7 ,4]

Exemple 1 :

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

Exemple 2 :

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

Idées de résolution de problèmes

(récursion) O(n)

Lorsque nous utilisons la récursivité pour répondre à cette question, ne le faites pas être induit en erreur par le titre, il devrait être clair Il y a trois fonctions de cette fonction : étant donné deux nœuds pp et qq

Si pp et qq existent, renvoie leur ancêtre commun s'il n'en existe qu'un, renvoie celui existant si aucun des deux ; pp ni qq existent, alors NULL est renvoyé. Cette question dit que les deux nœuds donnés existent, donc naturellement, cela peut être résolu en utilisant la fonction ci-dessus

Idées spécifiques : (1) Si la racine du nœud actuel est égale à NULL, alors NULL est renvoyé directement (2) Si rootroot est égal à pp ou qq, alors cet arbre doit renvoyer pp ou qq (3) Puis récursez les sous-arbres gauche et droit Parce qu'il est récursif, après avoir utilisé la fonction, on peut considérer que. les sous-arbres gauche et droit ont calculé les résultats, représentés par leftleft et rightright (4) À ce stade, si si leftleft est vide, alors le résultat final n'a besoin que de regarder rightright si rightright est vide, alors le résultat final n'a besoin que de regarder leftleft (5) Si leftleft et rightright sont tous deux non vides, car seuls deux nœuds pp et qq sont donnés, les deux ne sont pas vides, indiquant qu'un de chaque côté, donc rootroot est leur dernier ancêtre commun (6) Si leftleft et rightright sont tous deux vides, retournez vide (en fait déjà inclus dans le cas précédent)

La complexité temporelle est O(n) : chaque nœud Les points peuvent être parcourus au plus une fois ou en utilisant le théorème principal, et la complexité spatiale est O(n) : un espace de pile système est requis

code

/** 
* Definition for a binary tree node. 
* class TreeNode { 
* public $val = null; 
* public $left = null; 
* public $right = null; 
* function __construct($value) { 
    $this->val = $value; 
} 
 * } 
 */
 class Solution {
    /** 
    * @param TreeNode $root 
    * @param TreeNode $p 
    * @param TreeNode $q 
    * @return TreeNode 
    */
    function lowestCommonAncestor($root, $p, $q) {
        if ($root == null || $root == $p || $root == $q)
            return $root;
        $left = $this->lowestCommonAncestor($root->left, $p, $q);
        $right = $this->lowestCommonAncestor($root->right, $p, $q);
        
        //如果left为空，说明这两个节点在cur结点的右子树上，我们只需要返回右子树查找的结果即可
        if ($left == null)
            return $right;
        //同上
        if ($right == null)
            return $left;
        //如果left和right都不为空，说明这两个节点一个在cur的左子树上一个在cur的右子树上，
        //我们只需要返回cur结点即可。
        if ($left && $right) {
            return $root;
        }
        return null;
    }}

Apprentissage recommandé :

tutoriel vidéo php

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!