php实现判断树的子结构

一、总结

 很简单的递归判断

 

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

题目描述：

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

 

三、代码

代码一：php ac

1 
     val = $val; 9     }10 }*/11 function HasSubtree($pRoot1, $pRoot2)12 {13     // write code here14     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 };