题解 | #树的子结构#

算法思想一：递归

解题思路：

1.这道题判断是否是子结构，主要看pRoot2和pRoot1的根节点的值是否一样，一样的话再同时递归，
2.判断left节点，如果pRoot2的左节点为null,则说明pRoot2的left节点满足条件。
3.若pRoot2的节点不为null,并且pRoot1的left节点为null,或者说它们二者的值不一样，说明pRoot2不是pRoot1的子结构。
4.pRoot1和pRoot2的right节点和第2.3步一样的判断，当left和right同时成立，pRoot2才是pRoot1的子结构
5.因为题目约定空树不是任意一个数的子结构，所以pRoot1和pRoot2都不能为空，这是返回true的前提条件

代码展示：

Python版本

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def HasSubtree(self, pRoot1, pRoot2):
        # write code here
        # 递归
        def dfs(A, B):
            # 
            if not B:
                return True
            elif not A:
                return False
            elif A.val != B.val:
                return False
            # 对比A  B的左右子树是否相同
            return dfs(A.left, B.left) and dfs(A.right, B.right)
        # 特殊情况
        if not pRoot1&nbs***bsp;not pRoot2:
            return False
        # 递归计算 pRoot1, pRoot2 是否相同/pRoot1的左子树、右子树是否和pRoot2相同
        return dfs(pRoot1, pRoot2)&nbs***bsp;self.HasSubtree(pRoot1.left, pRoot2)&nbs***bsp;self.HasSubtree(pRoot1.right, pRoot2)

复杂度分析：

时间复杂度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。

算法思路二：非递归

解题思路：

1.先遍历树pRoot1，如果遍历到和pRoot2节点值相同的节点，进入isSubTree方法判断接下来的节点是否都相同
2.节点都相同返回True；不相同返回False，并且继续遍历树pRoot1找下一个相同的节点
3.如果遍历完了pRoot1还没有返回过True，说明pRoot2不是pRoot1的子结构，返回False
isSubTree方法：用于判断从pRoot1的子树是否有和pRoot2相同的部分

1.采用递归的思想，如果节点root1与root2的节点不同，则说明pRoot1的子树与pRoot2不具有相同的节点
2.如果值相同，则递归判断（isSubTree）他们各自得左右节点的值是不是相同

3.递归的终止条件时到达pRoot1或pRoot2的叶节点

代码展示：

JAVA版本

public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root2==null) return false;
        if(root1==null && root2!=null) return false;      
        boolean flag = false;
        if(root1.val==root2.val){
            // 两个节点相同时，验证以两个节点开始的子树是否相同
            flag = isSubTree(root1,root2);
        }
        if(!flag){
            // 递归左子树进行判断
            flag = HasSubtree(root1.left, root2);
            if(!flag){
                // 递归右子树进行判断
                flag = HasSubtree(root1.right, root2);
            }
        }
        return flag;
    }
    // 验证两颗树是否相同函数
    private boolean isSubTree(TreeNode root1, TreeNode root2) {
        if(root2==null) return true;
        if(root1==null && root2!=null) return false;      
        if(root1.val==root2.val){
            // 递归验证两个树的左右子树是否相同
            return isSubTree(root1.left, root2.left) &&  isSubTree(root1.right, root2.right);
        }else{
        return false;
        }
    }
}

复杂度分析：

时间复杂度：O(MN)，其中 M,N分别为树 pRoot1和树 pRoot2的节点数量；遍历pRoot1：O(m)，比较pRoot1和pRoot2：O(n)
空间复杂度：O(M)，最差的情况就是遍历了pRoot1的所有节点