How to get the nearest common ancestor of binary trees and binary search trees in PHP

Given a binary search tree, find the nearest common ancestor of two specified nodes in the tree. The definition of the nearest common ancestor in Baidu Encyclopedia is: "For two nodes p and q of a rooted tree T, the nearest common ancestor is represented as a node x, such that x is the ancestor of p and q and the depth of x is as large as possible ."

The nearest common ancestor of the binary search tree

Given a binary search tree , finds the nearest common ancestor of two specified nodes in this tree.

The definition of the nearest common ancestor in Baidu Encyclopedia is: "For two nodes p and q of a rooted tree T, the nearest common ancestor is represented as a node x, such that x is the ancestor of p and q and The depth of x is as large as possible (a node can also be its own ancestor)."

For example, given the following binary search tree: root = [6,2,8,0,4,7, 9,null,null,3,5]

Example 1:

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

Example 2:

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

Problem-solving ideas

This question asks you to find the nearest common ancestor of a binary search tree. The characteristic of a binary search tree is that all nodes in the left subtree are smaller than the current node, and all nodes in the right subtree are smaller than the current node. The nodes are all larger than the current node, and each subtree has the above characteristics, so this problem is easy to solve. Start traversing from the updated node

If the two node values ​​​​are less than the root node, it means that they are both at the root node On the left subtree of , we look to the left subtree. If both node values ​​are greater than the root node, it means they are both on the right subtree of the root node. We look to the right subtree. If a node value is greater than the root node, If the value of a node is less than the root node, it means that one of them is on the left subtree of the root node and the other is on the right subtree of the root node. Then the root node is their nearest common ancestor node.

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

The nearest common ancestor of a binary tree

Given a binary tree, find the The nearest common ancestor of two specified nodes in the tree.

The definition of the nearest common ancestor in Baidu Encyclopedia is: "For two nodes p and q of a rooted tree T, the nearest common ancestor is represented as a node x, such that x is the ancestor of p and q and The depth of ,null,7,4]

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

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

(Recursion) O(n)

When we use recursion to do this question, don’t be misled by the question. It should be clear that this function has three functions: given Two nodes pp and qq

If both pp and qq exist, return their common ancestor; if only one exists, return the existing one; if neither pp nor qq exists, return NULL. This question says If both given nodes exist, then the above function can naturally be used to solve the problem

Specific ideas: (1) If the current node rootroot is equal to NULL, then NULL is returned directly (2) If rootroot is equal to pp Or qq, then this tree must return pp or qq (3) Then recurse the left and right subtrees. Because it is recursive, after using the function, it can be considered that the left and right subtrees have calculated the results, represented by leftleft and rightright (4) At this time, if leftleft is Empty, then the final result only needs to look at rightright; if rightright is empty, then the final result only needs to look at leftleft (5) If leftleft and rightright are both non-empty, because only two nodes pp and qq are given, both are non-empty, indicating one on each side. , so rootroot is their latest common ancestor (6) If leftleft and rightright are both empty, return empty (actually already included in the previous case)

The time complexity is O(n): each time Each node can be traversed at most once or using the main theorem. The space complexity is O(n): system stack space is required

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

The above is the detailed content of How to get the nearest common ancestor of binary trees and binary search trees in PHP. For more information, please follow other related articles on the PHP Chinese website!