輸入兩棵二叉樹A，B，判斷B是不是A的子結構。（ps：我們約定空樹不是任意一個樹的子結構）
1.子樹的意思是包含了一個節(jié)點，就得包含這個節(jié)點下的所有節(jié)點,兩棵樹同時到底
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));

以上就是php如何實現二叉樹的子結構判斷（代碼）的詳細內容，更多請關注php中文網其它相關文章！