题目

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

题解

需要两个函数，一个用来判断A树是否包含B树。另一个判断A树和B树相同。

代码

<?php /*class TreeNode{ var $val; var $left = NULL; var $right = NULL; function __construct($val){ $this->val = $val; } }*/ function isSubtree($pRoot1, $pRoot2) { // write code here if($pRoot2 == null) return true; if($pRoot1 == null) return false; if($pRoot1->val ==$pRoot2->val){ return isSubtree($pRoot1->left, $pRoot2->left) && isSubtree($pRoot1->right, $pRoot2->right); } else{ return false; } } function HasSubtree($pRoot1, $pRoot2) { if ($pRoot1 == null || $pRoot2 == null) { return false; } return isSubtree($pRoot1, $pRoot2) || HasSubtree($pRoot1->left, $pRoot2) || HasSubtree($pRoot1->right, $pRoot2); }