剑指Offer - PHP树的子结构
题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
示例
输入：
{8,8,#,9,#,2,#,5},{8,9,#,2}
输出：
true
分析
- 先判断二叉树A、B的根节点是否相等。
- 如果根节点相等，则递归判断是否其左右节点是否相等。
- 如果根节点不相等，则判断是否有左右节点，从左右节点开始比较。
代码
// 树节点
class TreeNode{
var $val;
var $left = NULL;
var $right = NULL;
function __construct($val){
$this->val = $val;
}
}<?php
/**
* 判断是否为二叉树子结构
*
* @param object $pRoot1 二叉树A
* @param object $pRoot2 二叉树B
*/
function HasSubtree($pRoot1, $pRoot2)
{
return ($pRoot1 != null) && ($pRoot2 != null)
&& (isSubtree($pRoot1, $pRoot2) // 根节点是否相等
|| HasSubtree($pRoot1->left, $pRoot2) // 是否有左节点
|| HasSubtree($pRoot1->right, $pRoot2) // 是否有右节点
);
}
/**
* 递归判断节点值
*
* @param object $pRoot1 二叉树A
* @param object $pRoot2 二叉树B
*/
function isSubtree($pRoot1, $pRoot2)
{
if ($pRoot2 == NULL) return true; // B 树的子节点递归完时，返回 true
if ($pRoot1 == NULL) return false; // B 树节点不为空，但 A 树节点为空，直接返回 false。与上句代码顺序不可调换。
return $pRoot1->val == $pRoot2->val // 判断节点值是否相等
&& isSubtree($pRoot1->left, $pRoot2->left) // 递归左节点
&& isSubtree($pRoot1->right, $pRoot2->right); // 递归右节点
}
关于 LearnKu
粤公网安备 44030502004330号