树的子结构

输入两棵二叉树 A 和 B，判断 B 是不是 A 的子结构。(约定空树不是任意一个树的子结构)

B 是 A 的子结构， 即 A 中有出现和 B 相同的结构和节点值。

例如:
给定的树 A:

 3<br />    / \<br />   4   5<br />  / \<br /> 1   2<br />给定的树 B：

4
/
1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

输入：A = [1,2,3], B = [3,1]
输出：false

输入：A = [3,4,5,1,2], B = [4,1]
输出：true

一、递归

先简单过一下 100. 相同的树的递归逻辑。

1. 那道题是递归判断当前节点、左子树、右子树是否都同时相等。
2. 在实际写判断逻辑的时候，不必考虑如何满足左子树、右子树是否同时相等，那是递归自己去做的事情，
3. 我们只需要考虑当前节点是否相等就好，主要需要考虑一下，A、B 为空子树的情况。
4. 至于左右子树的判断，扔给递归就 ok 了。

   // 递归考察左子树、右子树
   return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);`
   

   这道题略有不同，问的是是否相似。于是就会有两个不同点：递归判断条件、递归判断范围

条件不同

相等要求的是对应的节点都相同，不能多也不能少。

而至于相似，如图

示例图上可以直观地看出，相似说明 A 可以在 B 结构的基础上有多余的子节点，即，允许子节点 B === null 的情况

// B 子树是空子树就 ok，无论 A 是否为 null
if(!B) {
    return true;
}

范围不同

1. 相等判断范围的是整棵树完全相同。
2. 而相似判断范围则是 B 与 A 的部分子树相同。
3. 那如何用代码来描述**部分子树**呢？
4. 或者换一个思路，实际上判断相等时，判断的起点是：A、B 的根节点。
5. 而判断相似，判断的起点变为了：B 的根节点 和 A 的任意节点

所以这里又需要递归来帮忙了…

var isSubStructure = function(A, B) {
  // ...
  return isSameTree(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B)
}

边界值

题目约定：约定空树不是任意一个树的子结构

var isSubStructure = function(A, B) {
  // 约定空树不是任意一个树的子结构
  if(A === null || B === null) {
      return false;
  }
  return isSameTree(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B)
}

var isSubStructure = function (A, B) {
  // 约定空树不是任意一个树的子结构
  if (A === null || B === null) {
    return false;
  }
  return isSameTree(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B)
};

var isSameTree = function (A, B) {
  // B子树是空子树 ok
  if (B === null) {
    return true;
  }
  // A子树是空子树 且 B 非空，不 ok
  // 当前两个节点的值不相等，不 ok
  if(A == null || A.val != B.val) {
    return false;
  }
  // 递归考察左子树、右子树
  return isSameTree(A.left, B.left) && isSameTree(A.right, B.right);
};

复杂度分析

时间复杂度

emmmmm 老师我不会……

就考虑最坏情况，如果 B 不是 A 子树

第一层递归 isSubStructure，则时间为 O (m) m 为 A 的节点数
第二层递归 isSameTree，如果 B 一直不为空就需要一直判断，直到 B 为空为止，所以是 O (n) n 为 B 节点的个数？
所以综合一下就是 O (m * n) ？

空间复杂度

这个真不知道…… （大学学的还给老师了……）

网上的说法是二叉树遍历的空间复杂度取决于树的高度 h，这里最坏情况下就是一条直的树枝没有分叉，所以就是 B 的高度 n，O (n)