另一棵树的子树

2025-08-27
作者 Y Y
~6.00K 字

另一棵树的子树

题目

给你两棵二叉树 root 和 subRoot 检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树如果存在，返回 true ,否则，返回 false 
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点tree 也可以看做它自身的一棵子树

示例 1：
输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true

示例 2：
输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false

解法1

思路:
暴力搜索,遍历每一个节点,判断节点及以下的树是否与subRoot相同,不同继续遍历下一个左右节点,相同返回true

代码:
public function isSubtree($s, $t)
{
    return $this->dfs($s, $t);
}

private function dfs($node1, $node2)
{
    // 直到主树结束
    if (!$node1) {
        return false;
    }

    // 验证节点及其下面的子树是否相同
    if ($this->check($node1, $node2)) {
        return true;
    }

    // 节点不相同,继续查询子节点是否相同
    return $this->dfs($node1->left, $node2) || $this->dfs($node1->right, $node2);
}

private function check($node1, $node2)
{
    // 不存在子节点,返回true
    if (!$node1 && !$node2) {
        return true;
    }

    // 值不同 || 存在一颗树有节点另一颗树没有节点的情况 返回false
    if ($node1->val !== $node2->val || !$node1 && $node2 || $node1 && !$node2) {
        return false;
    }

    // 继续比对子节点,直到不存在子节点
    return $this->check($node1->right, $node2->right) && $this->check($node1->left, $node2->left);
}

解法2

思路:
获取树的最大值,遍历整颗树写入数组中,缺少左右节点的用最大值填充,将数组转成字符串进行比较

代码:
private $sOrder = [];
private $tOrder = [];
private $maxElement;
private $lNull;
private $rNull;

private function getMaxElement($node)
{
    if ($node === null) {
        return;
    }
    $this->maxElement = max($this->maxElement, $node->val);
    $this->getMaxElement($node->left);
    $this->getMaxElement($node->right);
}

private function getDfsOrder($node, &$tar)
{
    if ($node === null) {
        return;
    }
    $tar[] = $node->val;
    if ($node->left !== null) {
        $this->getDfsOrder($node->left, $tar);
    } else {
        $tar[] = $this->lNull;
    }
    if ($node->right !== null) {
        $this->getDfsOrder($node->right, $tar);
    } else {
        $tar[] = $this->rNull;
    }
}

public function isSubtree($s, $t)
{
    $this->maxElement = PHP_INT_MIN;
    $this->sOrder     = [];
    $this->tOrder     = [];

    // 获取所有节点中最大的数值
    $this->getMaxElement($s);
    $this->getMaxElement($t);

    // 给末尾的节点设置两个节点,左节点数值为最大的数+1,右节点+2
    $this->lNull = $this->maxElement + 1;
    $this->rNull = $this->maxElement + 2;

    // 遍历整颗树,将节点的值写入数组中,如果不存在左节点或右节点,填充左右节点最大值+1或+2
    $this->getDfsOrder($s, $this->sOrder);
    $this->getDfsOrder($t, $this->tOrder);

    $strS = implode(',', $this->sOrder);
    $strT = implode(',', $this->tOrder);

    if (false !== $index = strpos($strS, $strT)) {
        if ($index > 0) {
            // 防止出现根节点部分相同,导致判断错误的情况
            if ($strS[$index - 1] !== ',') {
                return false;
            }
        }

        return true;
    }

    return false;
}

解法3

思路:
给主树的每个节点都计算一个hash值,hash值根据树当前节点的深度和值计算,子树计算根节点的hash值,
如果子树根节点的hash值在主树内存在,证明子树是主树的子树

代码:
const MAX_N = 1005;
const MOD = 1000000007;
public $p = [];

public $hS = [];
public $hT = [];

function getPrime()
{
    // 记录质数下标的数组
    $isPrime    = array_fill(0, self::MAX_N, true);
    $isPrime[0] = $isPrime[1] = false;
    // 记录质数的数组
    $primes = [];
    for ($i = 2; $i < self::MAX_N; $i++) {
        if ($isPrime[$i]) {
            // 下标为true,记录质数
            $this->p = $i;
        }

        foreach ($this->p as $prime) {
            if ($i * $prime >= self::MAX_N) {
                // 超过指定范围,break
                break;
            }

            // 指定不为质数的下标
            $isPrime[$prime * $i] = false;
            if ($i % $prime === 0) {
                // 防止重复设定质数下标
                break;
            }
        }
    }

    return $primes;
}

function dfs($o, &$h)
{
    // 获取每个节点对象在系统中的id,作为唯一键
    $id     = spl_object_id($o);
    $h[$id] = ["f" => $o->val, "s" => 1];

    if ($o->left === null && $o->right === null) {
        return;
    }
    if ($o->left !== null) {
        $this->dfs($o->left, $h);
        $lid         = spl_object_id($o->left);
        $h[$id]["s"] += $h[$lid]["s"];
        // hash值算法,左节点 31
        // 使用$this->p 降低哈希碰撞的概率,降低hash值重复的概率
        // % self::MOD用来限制结果不能大于self::MOD,防止结果溢出
        $h[$id]["f"] = ($h[$id]["f"] + (31 * $h[$lid]["f"] * $this->p[$h[$lid]["s"]]) % self::MOD) % self::MOD;
    }
    if ($o->right !== null) {
        $this->dfs($o->right, $h);
        $rid         = spl_object_id($o->right);
        $h[$id]["s"] += $h[$rid]["s"];
        // hash值算法,右节点 179
        // 使用$this->p 降低哈希碰撞的概率,降低hash值重复的概率
        // % self::MOD用来限制结果不能大于self::MOD,防止结果溢出
        $h[$id]["f"] = ($h[$id]["f"] + (179 * $h[$rid]["f"] * $this->p[$h[$rid]["s"]]) % self::MOD) % self::MOD;
    }
}

function isSubtree($s, $t)
{
    // 求质数
    $this->getPrime();
    // 将树s中每个节点的hash值记录到hS数组中
    $this->dfs($s, $this->hS);
    // 将树t中每个节点的hash值记录到hT数组中
    $this->dfs($t, $this->hT);

    // 获取树t根节点下标
    $tid = spl_object_id($t);
    // 获取树t根节点的hash值
    $tHash = $this->hT[$tid]["f"];

    foreach ($this->hS as $v) {
        // 查询树t根节点的hash值是否存在与hS中,存在证明树t是树s的子树
        if ($v["f"] === $tHash) {
            return true;
        }
    }

    return false;
}

每天进步一点点🤏

另一棵树的子树

题目

解法1

解法2

解法3