题解 | #树的子结构#

<?php

/*class TreeNode{
    var $val;
    var $left = NULL;
    var $right = NULL;
    function __construct($val){
        $this->val = $val;
    }
}*/

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param pRoot1 TreeNode类 
 * @param pRoot2 TreeNode类 
 * @return bool布尔型
 */
function HasSubtree( $pRoot1 ,  $pRoot2 )
{
    // write code here
    if ($pRoot1 == null || $pRoot2 == null) return false;
    if ($pRoot2->val == $pRoot1->val) {
        if (isEqual($pRoot1, $pRoot2)) return true;
    }
    $e1 = HasSubtree($pRoot1->left, $pRoot2);
    $e2 = HasSubtree($pRoot1->right, $pRoot2);
    return $e1 || $e2;
}
function isEqual($pRoot1, $pRoot2) {
    if ($pRoot2 == null) return true;
    if ($pRoot1 == null) return false;
    if ($pRoot1->val == $pRoot2->val) {
        $e1 = isEqual($pRoot1->left, $pRoot2->left);
        $e2 = isEqual($pRoot1->right, $pRoot2->right);
        return $e1 && $e2;
    } else {
        return false;
    }
}

参考大神的思路，在这自己写一下，方便复习：从A树的根节点开始，判断根节点值是否等于B树的根节点，如果是：那么就需要判断A树从当前节点起的子树是否和B树有相同的子结构，具体操作：用递归方法，每次先判断当前节点值A B树是否相等，如果不等，直接返回表明A树当前节点起没有和B树相同的子结构，如果相等，就判断A树的左子树是否和B树的左子树的结构是否相同，判断A树的右子树的结构是否和B树的右子树的结构相同，取这种两个子树判断结果的与运算值，递归结束的条件是B树遍历完；如果不是：就取A树的左子树或者右子树去寻找。时间复杂度是logn