输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
前面曾经做过根据中序和前序的访问顺序，重新构建二叉树，所以根据中序和前序同样可以确定一个二叉树。当时是递归的构建。将构建的过程反过来。确定一个二叉树是不是另一个二叉树的子树可以分别进行前序和中序便利，如果一个树的前序和中序的遍历的子序列分别包含了另一个树的前序和中序的访问，那么后者一定是前者的子树。
class TreeNode{
var $val;
var $left = NULL;
var $right = NULL;
function __construct($val){
$this->val = $val;
}
}
$pre_root1 = array();
$pre_root2 = array();
$in_root1 = array();
$in_root2 = array();
function HasSubtree($pRoot1, $pRoot2)
{
GLOBAL $pre_root1;
GLOBAL $pre_root2;
GLOBAL $in_root1;
GLOBAL $in_root2;
preOrder($pRoot1,$pre_root1);
preOrder($pRoot2,$pre_root2);
inOrder($pRoot1,$in_root1);
inOrder($pRoot2,$in_root2);
$pre_root1_str = implode('',$pre_root1);
$pre_root2_str = implode('',$pre_root2);
$in_root1_str = implode('',$in_root1);
$in_root2_str = implode('',$in_root2);
if(strpos($pre_root1_str,$pre_root2_str)!==false && strpos($in_root1_str,$in_root2_str)!==false){
return true;
}
else{
return false;
}
}
function preOrder($root,&$arr){
if($root==null){
return ;
}
else{
$arr[] = $root->val;
preOrder($root->left, $arr);
preOrder($root->right, $arr);
}
}
function inOrder($root,&$arr){
if($root==null){
return;
}
else{
inOrder($root->left, $arr);
$arr[] = $root->val;
inOrder($root->right, $arr);
}
}
$root1 = new TreeNode(8);
$root1->left = new TreeNode(8);
$root1->right = new TreeNode(7);
$root1->left->left = new TreeNode(9);
$root1->left->right = new TreeNode(2);
$root2 = new TreeNode(8);
$root2->left = new TreeNode(9);
$root2->right = new TreeNode(2);
echo HasSubtree($root1, $root2);
这样是判断是否是子树，而不是子结构，子结构和子树是有区别的，子结构的范围要广。
因为树本身是一种递归结构，所以可以考虑递归的比较。判断是否为子结构的时候非常方便的,可以通过递归 的方式逐次比较，判断是不是子结构，同样可以递归的比较。
function HasSubtree($pRoot1, $pRoot2)
{
if($pRoot1==null&&$pRoot2!=null){//p1的范围小于p2
return false;
}
if ($pRoot2==null){//空树不是任意一个树的子结构
return false;
}
$flag |= isEqualStruct($pRoot1, $pRoot2);
if ($flag) {
return $flag;
}
$flag |= HasSubtree($pRoot1->left, $pRoot2);
if ($flag) {
return $flag;
}
$flag |= HasSubtree($pRoot1->right, $pRoot2);
return $flag;
}
//判断结构相同，而不是判断树相同
function isEqualStruct($pRoot1,$pRoot2){
$flag = true;
if ($pRoot2==null){//p2为空，说明p1的范围大于等于p2
return true;
}else if($pRoot1!=null&&$pRoot2!=null){//都不为空接着比较，直到比较出不同。
if ($pRoot1->val==$pRoot2->val){//对应节点上的值相同进一步比较
if($flag==true){
$flag &= isEqualStruct($pRoot1->left,$pRoot2->left);
}
if($flag==true){
$flag &= isEqualStruct($pRoot1->right,$pRoot2->right);
}
}else{//值不相同就可以返回假了
return false;
}
}else{//这里是p1等于空，但是p2不等于空的情况说明p2的范围要大于p1，p2不是p1的子结构。
return false;
}
return $flag;
}
题目描述
操作给定的二叉树，将其变换为源二叉树的镜像。
输入描述:
二叉树的镜像定义：源二叉树
8
/
6 10
/ \ /
5 7 9 11
镜像二叉树
8
/
10 6
/ \ /
11 9 7 5
function Mirror(&$root)
{
if($root==NULL){
return;
}
$t = $root->left;
$root->left = $root->right;
$root->right = $t;
Mirror($root->left);
Mirror($root->right);
}
.
