LeetCode题解：一棵树是否是另一棵树的子树

题目描述

给你两棵二叉树root和subRoot 。检验root中是否包含和subRoot具有相同结构和节点值的子树。如果存在，返回true；否则，返回false。
二叉树tree的一棵子树包括tree的某个节点和这个节点的所有后代节点。tree也可以看作它自身的一棵子树。

示例

• 示例1
  输入：root = [3,4,5,1,2], subRoot = [4,1,2]
  输出：true
  示例1
• 示例2
  输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
  输出：false
  示例2

思路方法

将是否是子树问题转化为是否相等的问题
判断两树是否相等有三个条件：

• 当前两个树的根节点值相等；
• 并且，s的左子树和t的左子树相等；
• 并且，s的右子树和t的右子树相等。
  而判断t是否是s的子树有三个或条件
• 当前两棵树相等；
• 或t是s的左子树；
• 或t是s的右子树。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        return dfs(root,subRoot);
    }
    public boolean dfs(TreeNode root,TreeNode subRoot){
        if(root==null){
            return false;
        }
        return check(root,subRoot)||dfs(root.left,subRoot)||dfs(root.right,subRoot);
    }
    public boolean check(TreeNode root,TreeNode subRoot){
        if(root==null&&subRoot==null){
            return true;
        }
        if(root==null||subRoot==null||root.val!=subRoot.val){
            return false;
        }
        return check(root.left,subRoot.left)&&check(root.right,subRoot.right);
    }
}