PHP에서 이진 트리와 이진 검색 트리의 가장 가까운 공통 조상을 얻는 방법

이진 검색 트리가 주어지면 트리에서 지정된 두 노드의 가장 가까운 공통 조상을 찾습니다. 바이두 백과사전에서 가장 가까운 공통 조상에 대한 정의는 다음과 같습니다. "뿌리 트리 T의 두 노드 p와 q에 대해 가장 가까운 공통 조상은 노드 x로 표시됩니다. 즉, x는 p와 q의 조상이고 깊이는 x는 가능한 한 크다.”

이진 검색 트리의 최소 공통 조상

이진 검색 트리가 주어지면 트리에 지정된 두 노드의 가장 가까운 공통 조상을 찾습니다.

바이두 백과사전에서 가장 가까운 공통 조상의 정의는 다음과 같습니다. "뿌리 트리 T의 두 노드 p와 q에 대해 가장 가까운 공통 조상은 노드 x로 표시됩니다. 즉, x는 p와 q의 조상이고 깊이는 of x는 클 수 있습니다(노드가 자신의 조상일 수도 있음) "

예를 들어 다음 이진 검색 트리가 주어지면: root = [6,2,8,0,4,7,9,null,null, 3, 5]

예제 1:

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

예제 2:

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

문제 해결 아이디어

이 질문은 이진 검색 트리의 가장 가까운 공통 조상을 찾도록 요청하며, 이진 검색 트리는 왼쪽 자식입니다. 트리의 모든 노드는 현재 노드보다 작고, 오른쪽 하위 트리의 모든 노드는 현재 노드보다 크며, 각 하위 트리는 위와 같은 특성을 가지므로 이 문제는 쉽게 해결할 수 있습니다. 업데이트된 노드에서 순회

두 노드 값이 모두 루트 노드보다 작으면 둘 다 루트 노드의 왼쪽 하위 트리에 있음을 의미하며 값이 왼쪽 하위 트리를 찾습니다. 두 노드의 값이 루트 노드보다 크다는 것은 둘 다 루트 노드의 오른쪽 하위 트리에 있음을 의미하며, 노드 값이 루트 노드보다 크고 노드 값이 다음과 같은 경우 오른쪽 하위 트리를 찾습니다. 루트 노드보다 작으면 그 중 하나는 루트 노드의 왼쪽 하위 트리에 있고 다른 하나는 루트 노드의 오른쪽 하위 트리에 있으며 루트 노드는 가장 가까운 공통 조상 노드입니다.

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

이진 트리의 최소 공통 조상

이진 트리가 주어지면 트리에 지정된 두 노드의 가장 가까운 공통 조상을 찾습니다.

바이두 백과사전에서 가장 가까운 공통 조상의 정의는 다음과 같습니다. "뿌리 트리 T의 두 노드 p와 q에 대해 가장 가까운 공통 조상은 노드 x로 표시됩니다. 즉, x는 p와 q의 조상이고 깊이는 of x는 클 수 있습니다(노드가 자신의 조상이 될 수도 있음)”

예를 들어 다음 이진 트리가 주어지면: root = [3,5,1,6,2,0,8,null,null,7 ,4]

예 1:

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

예 2:

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

문제 해결 아이디어

(재귀) O(n)

재귀를 사용하여 이 질문을 수행할 때 다음을 수행하지 마세요. 제목으로 오해할 수 있습니다. 이 함수에는 세 가지 기능이 있습니다. 두 개의 노드 pp와 qq가 주어지면

pp와 qq가 모두 존재하는 경우 둘 다 존재하면 공통 조상을 반환하고 둘 다 없으면 기존 노드를 반환합니다. pp 또는 qq가 존재하면 NULL이 반환됩니다. 이 질문은 주어진 두 노드가 존재한다는 것을 의미하므로 자연스럽게 위 함수를 사용하여 해결할 수 있습니다

구체적인 아이디어: (1) 현재 노드 루트 루트가 NULL과 같으면 NULL이 직접 반환됩니다. (2) rootroot가 pp 또는 qq와 같으면 이 트리는 pp 또는 qq를 반환해야 합니다. (3) 그러면 왼쪽 및 오른쪽 하위 트리가 재귀적이므로 함수를 사용한 후에는 다음과 같이 간주할 수 있습니다. 왼쪽 및 오른쪽 하위 트리는 leftleft 및 rightright로 표시되는 결과를 계산했습니다. (4) 이때 leftleft가 비어 있으면 최종 결과는 rightright가 비어 있으면 rightright만 보면 됩니다. leftleft를 살펴보려면 (5) leftleft와 rightright가 둘 다 비어 있지 않은 경우, 두 개의 노드 pp와 qq만 주어지기 때문에 둘 다 비어 있지 않습니다. 이는 양쪽에 하나가 있으므로 rootroot가 이들의 최신 공통 조상임을 나타냅니다. (6) leftleft와 rightright가 모두 비어 있으면 비어 있음을 반환합니다(실제로는 이전 사례에 이미 포함되어 있음)

시간 복잡도는 O(n)입니다. 각 노드 포인트는 최대 한 번 또는 주 정리를 사용하여 탐색할 수 있으며 공간 복잡도는 다음과 같습니다. O(n): 시스템 스택 공간이 필요합니다

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

추천 학습:php 비디오 튜토리얼

위 내용은 PHP에서 이진 트리와 이진 검색 트리의 가장 가까운 공통 조상을 얻는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!