树的子结构

---

题目：

题解：

1、先序遍历 + 包含判断

• 解题思路：若树 B 是树 A 的子结构，则子结构的根节点可能为树 A 的任意一个节点。因此，判断树 B 是否是树 A 的子结构，需完成以下两步工作：

  1. 先序遍历树 A 中的每个节点 nA ；（对应函数 isSubStructure(A, B)）
  2. 判断树 A 中 以 nA 为根节点的子树 是否包含树 B 。（对应函数 recur(A, B)）

• 复杂度分析：

  • 时间复杂度 O(MN) ： 其中 M,N分别为树 A 和 树 B 的节点数量；先序遍历树 A 占用 O(M) ，每次调用 recur(A, B) 判断占用 O(N) 。
  • 空间复杂度 O(M) ： 当树 A 和树 B 都退化为链表时，递归调用深度最大。当 M≤N 时，遍历树 A 与递归判断的总递归深度为 M ；当 M>N 时，最差情况为遍历至树 A 叶子节点，此时总递归深度为 M。

• 代码：

  // 通过前序遍历的深度遍历法的思想
  public class Solution {
      // 先序遍历树 A 中的每个节点
      public boolean isSubStructure(TreeNode A, TreeNode B) {
          // 1. 判断A和B是否为空，因为约定空树不是任意一个树的子结构，所以直接返回false
          if (A == null || B == null) {
              return false;
          }
          // 2. 根据前序遍历判断
          return recur(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B);
      }
  
      // 判断树 A 中 以 nA 为根节点的子树 是否包含树 B
      boolean recur(TreeNode A, TreeNode B) {
          // B为空了，说明B的全部结点和A的子节点全部匹配上了
          if (B == null) return true;
          // A的结点为空，B的结点不为空；或者A的结点和B的结点不同；都说明不匹配
          if (A == null || A.val != B.val) return false;
          // 到这里说明A和B的值相等，接下来判断他们的left和right
          return recur(A.left,B.left) && recur(A.right,B.right);
      }
  }