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 restree1HasTreeB(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)

 ?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如何实现二叉树的子结构判断（代码）的详细内容，PHP教程

郑重声明：本文版权归原作者所有，转载文章仅为传播更多信息之目的，如作者信息标记有误，请第一时间联系我们修改或删除，多谢。