php实现判断树的子结构

一、总结

很简单的递归判断

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

题目描述：

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

三、代码

代码一：php ac

 <?php

 /*class TreeNode{

     var $val;

     var $left = NULL;

     var $right = NULL;

     function __construct($val){

         $this->val = $val;

     }

 }*/

 function HasSubtree($pRoot1, $pRoot2)

 {

     // write code here

     if($pRoot1 == NULL || $pRoot2 == NULL){ //1、空值判断

         return false;

     }

     return isSubtree($pRoot1, $pRoot2) ||

         HasSubtree($pRoot1->left, $pRoot2) || HasSubtree($pRoot1->right, $pRoot2);

 }

 function isSubtree($pRoot1, $pRoot2){

     if( $pRoot2 == NULL){

         return true;

     }

     if($pRoot1 == NULL){

         return false;

     }

     return $pRoot1->val == $pRoot2->val && isSubtree($pRoot1->left, $pRoot2->left) && isSubtree($pRoot1->right, $pRoot2->right); //2、递归判断

 }

代码二：

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

 class Solution {

     bool isSubtree(TreeNode* pRootA, TreeNode* pRootB) {

         if (pRootB == NULL) return true;

         if (pRootA == NULL) return false;

         if (pRootB->val == pRootA->val) {

             return isSubtree(pRootA->left, pRootB->left)

                 && isSubtree(pRootA->right, pRootB->right);

         } else return false;

     }

 public:

     bool HasSubtree(TreeNode* pRootA, TreeNode* pRootB)

     {

         if (pRootA == NULL || pRootB == NULL) return false;

         return isSubtree(pRootA, pRootB) ||

             HasSubtree(pRootA->left, pRootB) ||

             HasSubtree(pRootA->right, pRootB);

     }

 };