力扣--LCR 143. 子结构判断

题目

给定两棵二叉树 tree1 和 tree2，判断 tree2 是否以 tree1 的某个节点为根的子树具有 相同的结构和节点值 。
注意，空树 不会是以 tree1 的某个节点为根的子树具有 相同的结构和节点值 。

示例 1：

代码

/**

• 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 isSubStructure(TreeNode A, TreeNode B) {
  if(A == null || B == null){
  return false;
  }

   if(isSubTree(A, B)){
       return true;
   }
  
   if(isSubStructure(A.left, B) || isSubStructure(A.right, B)){
       return true;
   }
  
   return false;
  

  }

  public boolean isSubTree(TreeNode Ta, TreeNode Tb){
  if(Tb == null){
  return true;
  }

   if(Ta == null){
       return false;
   }
  
   if(Ta.val != Tb.val){
       return false;
   }
  
   return isSubTree(Ta.left, Tb.left) &&
          isSubTree(Ta.right, Tb.right);
  

  }
  }
  假设树A的节点个数为 n, 树B为k，则
  时间复杂度：isSubTree函数的时间复杂度为 O(k)，所以时间复杂度为 O(n*k)。
  空间复杂度：空间复杂度为树 A 的高度。