[PHP] 算法-二叉树的子结构判断的PHP实现

输入两棵二叉树a，b，判断b是不是a的子结构。（ps：我们约定空树不是任意一个树的子结构）
1.子树的意思是包含了一个节点，就得包含这个节点下的所有节点,两棵树同时到底
2.子结构可以是a树的任意一部分


思路：
1.第一个递归：a和b两棵树，先在a中找到与b的根结点相同的点，如果a的根不是，那就递归a的左右子树来找
2.第二个递归：从两棵树的根结点开始进行比较，遍历的过程中，如果b树为空，则返回true;如果b不为空，a为空，返回false
              a树的结点值与b树的不同，返回false;
              短路运算符&& ，递归a的左子树，b的左子树；递归a的右子树，b的右子树

hassubtree(treea,treeb)
    if(treea->val==treeb->val)//根结点相同
        res=tree1hastreeb(treea.treeb)
    if !res
        res=hassubtree(treea->left.treeb)//第一层遍历
    if !res
        res=hassubtree(treea->right.treeb)//第一层遍历
    return res
tree1hastreeb(treea,treeb)
    //顺序不能变
    if treeb==null  //b到底的时候，就是true
        return true
    if treea==null
        return false//b没到底，a到底了，就是false
    if treea->val!=treeb->val //a和b的结点没对上
        return false
    //短路语法 ，如果前面的是false，直接返回false,后面不用走
    return tree1hastreeb(treea->left,treeb->left)&&tree1hastreeb(treea->right,treeb->right)

 

<?php
class treenode{
    public $val;
    public $left = null;
    public $right = null;
    public function __construct($val){
        $this->val = $val;
    }   
}


//构造两棵树
$node1=new treenode(1);
$node2=new treenode(2);
$node3=new treenode(3);
$node4=new treenode(4);
$node5=new treenode(5);


$treea=$node1;
$node1->left=$node2;
$node1->right=$node3;
$node3->left=$node4;
$node3->right=$node5;

//var_dump($treea);

$node6=new treenode(3);
$node7=new treenode(4);
$node6->left=$node7;
$treeb=$node6;
//var_dump($treeb);

function hassubtree($proot1,$proot2){
        $res=false;
        if($proot1==null || $proot2==null) return $res;
        if($proot1->val==$proot2->val) $res=tree1hastree2($proot1,$proot2);
        if(!$res) $res=hassubtree($proot1->left,$proot2);
        if(!$res) $res=hassubtree($proot1->right,$proot2);
        return $res;
}
function tree1hastree2($treea,$treeb){
        if($treeb==null) return true;
        if($treea==null) return false;
        if($treea->val!=$treeb->val) return false;
        return tree1hastree2($treea->left,$treeb->left)&&tree1hastree2($treea->right,$treeb->right);
}
var_dump(hassubtree($treea,$treeb));