輸入兩棵二叉樹(shù)A，B，判斷B是不是A的子結(jié)構(gòu)。（ps：我們約定空樹(shù)不是任意一個(gè)樹(shù)的子結(jié)構(gòu)）
1.子樹(shù)的意思是包含了一個(gè)節(jié)點(diǎn)，就得包含這個(gè)節(jié)點(diǎn)下的所有節(jié)點(diǎn),兩棵樹(shù)同時(shí)到底
2.子結(jié)構(gòu)可以是A樹(shù)的任意一部分
思路：
1.第一個(gè)遞歸：A和B兩棵樹(shù)，先在A中找到與B的根結(jié)點(diǎn)相同的點(diǎn)，如果A的根不是，那就遞歸A的左右子樹(shù)來(lái)找
2.第二個(gè)遞歸：從兩棵樹(shù)的根結(jié)點(diǎn)開(kāi)始進(jìn)行比較，遍歷的過(guò)程中，如果B樹(shù)為空，則返回true;如果B不為空，A為空，返回false
A樹(shù)的結(jié)點(diǎn)值與B樹(shù)的不同，返回false;
短路運(yùn)算符 ，遞歸A的左子樹(shù)，B的左子樹(shù)；遞歸A的右子樹(shù)，B的右子樹(shù)

HasSubtree(treeA,treeB) if(treeA- val==treeB- val)//根結(jié)點(diǎn)相同 res=tree1HasTreeB(treeA.treeB) if !res res=HasSubtree(treeA- left.treeB)//第一層遍歷 if !res res=HasSubtree(treeA- right.treeB)//第一層遍歷 return restree1HasTreeB(treeA,treeB) //順序不能變 if treeB==null //B到底的時(shí)候，就是true return true if treeA==null return false//B沒(méi)到底，A到底了，就是false if treeA- val!=treeB- val //A和B的結(jié)點(diǎn)沒(méi)對(duì)上 return false //短路語(yǔ)法 ，如果前面的是false，直接返回false,后面不用走 return tree1HasTreeB(treeA- left,treeB- left) tree1HasTreeB(treeA- right,treeB- right)

 ?phphtml' target='_blank'>class TreeNode{ public $val; public $left = NULL; public $right = NULL; public function __construct($val){ $this- val = $val;
 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如何實(shí)現(xiàn)二叉樹(shù)的子結(jié)構(gòu)判斷（代碼）的詳細(xì)內(nèi)容，PHP教程

鄭重聲明：本文版權(quán)歸原作者所有，轉(zhuǎn)載文章僅為傳播更多信息之目的，如作者信息標(biāo)記有誤，請(qǐng)第一時(shí)間聯(lián)系我們修改或刪除，多謝。