题解 | #判断t1树中是否有与t2树完全相同的子树#

方法一（递归）

1.题意整理

• 给定彼此独立的两棵二叉树t1和t2，树中节点各不相同。
• 判断t2是否是t1的子树。

2.思路整理

首先定义一个函数，用来判断两颗树是否完全相同。然后根据这个函数，通过递归的方式遍历t1中所有的子树，看有没有和t2完全相同的。

• 递归终止条件：如果root1、root2同时为空，说明所有节点都满足要求，返回true。如果root1为空，root2不为空或者root2为空，root1不为空，说明不满足要求，返回false。
• 递归如何传递：每次递归，都要比较当前节点root1和root2相等，同时比较root1左子节点是否等于root2左子节点，root1右子节点是否等于root2右子节点。
• 递归的返回值：返回当前层节点是否符合两棵树完全相同的要求。

图解展示：

3.代码实现

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root1 TreeNode类 
     * @param root2 TreeNode类 
     * @return bool布尔型
     */
    public boolean isContains (TreeNode root1, TreeNode root2) {
        //t1遍历完，还没找到t2，直接返回false
        if(root1==null) return false;
        //遍历t1中所有子树，看有没有与t2完全相同的
        return equals(root1,root2)||isContains(root1.left,root2)||isContains(root1.right,root2);
    }
    
    //判断两棵树是否完全相同
    private boolean equals(TreeNode root1, TreeNode root2){
        //如果同时为空，返回true
        if(root1==null&&root2==null) return true;
        //只有其中一个为空，返回false
        if(root1==null||root2==null) return false;
        //要求当前节点相等，并且左子树和右子树节点均相等
        return root1.val==root2.val&&equals(root1.left,root2.left)&&equals(root1.right,root2.right);
    }
}

4.复杂度分析

• 时间复杂度：需要遍历二叉树中所有的节点，所以时间复杂度是$O(n)O(n)$。
• 空间复杂度：需要额外深度为n的递归栈开销，所以空间复杂度为$O(n)O(n)$。