So erhalten Sie den nächsten gemeinsamen Vorfahren von Binärbäumen und binären Suchbäumen in PHP

Suchen Sie anhand eines binären Suchbaums den nächsten gemeinsamen Vorfahren zweier angegebener Knoten im Baum. Die Definition des nächsten gemeinsamen Vorfahren in der Baidu-Enzyklopädie lautet: „Für zwei Knoten p und q eines Wurzelbaums T wird der nächste gemeinsame Vorfahre als Knoten x dargestellt, sodass x der Vorfahre von p und q und die Tiefe von ist x ist so groß wie möglich.

Die Definition des nächsten gemeinsamen Vorfahren in der Baidu-Enzyklopädie lautet: „Für zwei Knoten p und q eines Wurzelbaums T wird der nächste gemeinsame Vorfahre als Knoten x dargestellt, sodass x der Vorfahre von p und q und die Tiefe ist.“ von x ist Kann groß sein (ein Knoten kann auch sein eigener Vorfahre sein) 3, 5]

Beispiel 1:

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

Beispiel 2:

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

Ideen zur Problemlösung

Bei dieser Frage geht es darum, den nächsten gemeinsamen Vorfahren eines binären Suchbaums und das Merkmal von a zu finden Der binäre Suchbaum ist das linke Kind. Alle Knoten des Baums sind kleiner als der aktuelle Knoten, alle Knoten des rechten Teilbaums sind größer als der aktuelle Knoten und jeder Teilbaum weist die oben genannten Eigenschaften auf, sodass dieses Problem leicht zu lösen ist vom aktualisierten Knoten

Wenn die beiden Knotenwerte beide kleiner als der Wurzelknoten sind, bedeutet dies, dass sie sich beide im linken Teilbaum des Wurzelknotens befinden. Wenn die Werte von Beide Knoten sind größer als der Wurzelknoten. Dies bedeutet, dass sie sich beide im rechten Teilbaum des Wurzelknotens befinden. Wenn der Wert eines Knotens größer als der Wurzelknoten ist und der Wert eines Knotens kleiner ist Als der Wurzelknoten bedeutet dies, dass sich einer von ihnen im linken Teilbaum des Wurzelknotens und der andere im rechten Teilbaum des Wurzelknotens befindet. Dann ist der Wurzelknoten der nächstgelegene gemeinsame Vorfahrenknoten.

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;
    }}

Kleinster gemeinsamer Vorfahre des Binärbaums

Suchen Sie bei einem gegebenen Binärbaum den nächsten gemeinsamen Vorfahren der beiden angegebenen Knoten im Baum.

Die Definition des nächsten gemeinsamen Vorfahren in der Baidu-Enzyklopädie lautet: „Für zwei Knoten p und q eines Wurzelbaums T wird der nächste gemeinsame Vorfahre als Knoten x dargestellt, sodass x der Vorfahre von p und q und die Tiefe ist.“ von x ist Kann groß sein (ein Knoten kann auch sein eigener Vorfahre sein) ”

Gegeben sei beispielsweise der folgende Binärbaum: root = [3,5,1,6,2,0,8,null,null,7 ,4]

Beispiel 1:

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

Beispiel 2:

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

Ideen zur Problemlösung

(rekursion) O(n)

Wenn wir für diese Frage Rekursion verwenden, tun Sie das nicht Lassen Sie sich vom Titel in die Irre führen, es sollte klar sein, dass es drei Funktionen dieser Funktion gibt: Wenn sowohl pp als auch qq vorhanden sind, geben Sie ihren gemeinsamen Vorfahren zurück. Wenn keiner vorhanden ist, geben Sie den vorhandenen zurück pp noch qq existieren, dann wird NULL zurückgegeben. Diese Frage besagt, dass die angegebenen zwei Knoten vorhanden sind, sodass sie natürlich mithilfe der obigen Funktion gelöst werden kann. Spezifische Ideen: (1) Wenn der aktuelle Knoten rootroot gleich NULL ist, dann NULL wird direkt zurückgegeben. (2) Wenn rootroot gleich pp oder qq ist, muss dieser Baum pp oder qq zurückgeben. (3) Dann werden die linken und rechten Teilbäume rekursiv betrachtet, nachdem die Funktion verwendet wurde Die linken und rechten Teilbäume haben die Ergebnisse berechnet, dargestellt durch leftleft und rightright (4). Wenn leftleft leer ist, muss das Endergebnis nur nach rightright betrachtet werden. Wenn rightright leer ist, muss das Endergebnis nur angezeigt werden betrachten leftleft (5) Wenn leftleft und rightright beide nicht leer sind, da nur zwei Knoten pp und qq angegeben sind, sind beide nicht leer, was darauf hinweist, dass auf jeder Seite einer ist, sodass rootroot ihr letzter gemeinsamer Vorfahre ist (6) Wenn leftleft und rightright beide leer sind, geben Sie leer zurück (tatsächlich bereits im vorherigen Fall enthalten)

Die Zeitkomplexität ist O(n): Jeder Knotenpunkte können höchstens einmal oder unter Verwendung des Hauptsatzes durchlaufen werden, und die Raumkomplexität beträgt O(n): System-Stack-Speicherplatz ist erforderlich

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;
    }}

Empfohlenes Lernen:php-Video-Tutorial

Das obige ist der detaillierte Inhalt vonSo erhalten Sie den nächsten gemeinsamen Vorfahren von Binärbäumen und binären Suchbäumen in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!