php实现判断树的子结构

一、总结

很简单的递归判断

二、php实现判断树的子结构

题目描述：

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

三、代码

代码一：php ac

 1 <?php
 2  
 3 /*class TreeNode{
 4     var $val;
 5     var $left = NULL;
 6     var $right = NULL;
 7     function __construct($val){
 8         $this->val = $val;
 9     }
10 }*/
11 function HasSubtree($pRoot1, $pRoot2)
12 {
13     // write code here
14     if($pRoot1 == NULL || $pRoot2 == NULL){ //1、空值判断
15         return false;
16     }
17     return isSubtree($pRoot1, $pRoot2) ||
18         HasSubtree($pRoot1->left, $pRoot2) || HasSubtree($pRoot1->right, $pRoot2);
19 }
20  
21 function isSubtree($pRoot1, $pRoot2){
22     if( $pRoot2 == NULL){
23         return true;
24     }
25     if($pRoot1 == NULL){
26         return false;
27     }
28     return $pRoot1->val == $pRoot2->val && isSubtree($pRoot1->left, $pRoot2->left) && isSubtree($pRoot1->right, $pRoot2->right); //2、递归判断
29 }

代码二：

利用好短路特性，完全不用那么多flag

 1 class Solution {
 2     bool isSubtree(TreeNode* pRootA, TreeNode* pRootB) {
 3         if (pRootB == NULL) return true;
 4         if (pRootA == NULL) return false;
 5         if (pRootB->val == pRootA->val) {
 6             return isSubtree(pRootA->left, pRootB->left)
 7                 && isSubtree(pRootA->right, pRootB->right);
 8         } else return false;
 9     }
10 public:
11     bool HasSubtree(TreeNode* pRootA, TreeNode* pRootB)
12     {
13         if (pRootA == NULL || pRootB == NULL) return false;
14         return isSubtree(pRootA, pRootB) ||
15             HasSubtree(pRootA->left, pRootB) ||
16             HasSubtree(pRootA->right, pRootB);
17     }
18 };