树的子结构

题目描述

示例

代码

代码1 递归判断

/*
基本思路，遍历大树，找到与子结构根节点相同的节点
然后传入判断函数进行遍历比较
*/
function HasSubtree(pRoot1, pRoot2)
{
    if(!pRoot1 || !pRoot2) return false
    
    // 
    if(pRoot1.val === pRoot2.val){
        if( judge(pRoot1, pRoot2) ){
            return true
        }
    }
    
    // 遍历左孩子或者右孩子
    return HasSubtree(pRoot1.left, pRoot2) || HasSubtree(pRoot1.right, pRoot2)
    
    // 判断是否是子结构，返回true或false
    function judge(root, subTree){
        // 终止条件
        if(subTree === null){ // 子树遍历完了，说明全部匹配
            return true
        }
        if(root === null){ // 如果大树遍历完了，表示没有匹配
            return false
        }
        
        // 遍历它俩，如果相等的话，继续往下比对
        if(root.val === subTree.val){
            // 左边和右边都得相等
            return judge(root.left, subTree.left) && judge(root.right, subTree.right)
        }
        
        // 如果有不相等的，直接返回
        return false
    }
    
}

时间复杂度O(MN)：其中 M,N分别为树 pRoot1和 树 pRoot2的节点数量；先序遍历树pRoot1 占用 O(M)，每次调用 dfs(A, B) 判断占用 O(N)。

空间复杂度O(M)：当树 pRoot1 和树 pRoot2 都退化为链表时，递归调用深度最大。当 M≤N 时，遍历树pRoot1 与递归判断的总递归深度为 M ；当 M>N 时，最差情况为遍历至树pRoot1叶子节点，此时总递归深度为 M。

题目来源

JZ26 树的子结构