leetcode 链接：检查子树

题目

检查子树。你有两棵非常大的二叉树：T1，有几万个节点；T2，有几万个节点。设计一个算法，判断 T2 是否为 T1 的子树。
如果 T1 有这么一个节点 n，其子树与 T2 一模一样，则 T2 为 T1 的子树，也就是说，从节点 n 处把树砍断，得到的树与 T2 完全相同。

注意：此题相对书上原题略有改动。

示例：

  1. 输入：t1 = [1, 2, 3], t2 = [2]
  2. 输出：true
  4. 输入：t1 = [1, null, 2, 4], t2 = [3, 2]
  5. 输出：false

解答 & 代码

如果 t2 是 t1 的子树，那么需满足以下三种情况的任意一种：

  • t1 和 t2 是同一棵树（调用另外的函数检查两棵树是否为同一棵树）
    • 如果 t1 和 t2 是同一棵树，那么需满足如下条件：
      • t1 和 t2 指针相同，就是同一个节点，那么这两棵树当然就是同一棵树
      • 同时满足如下三个条件：
        • t1 和 t2 节点值相同
        • t1 的左子树和 t2 的左子树相同
        • t1 的右子树和 t2 的右子树相同
  • t2 是 t1 左子树某个节点的子树（递归）
  • t2 是 t1 右子树某个节点的子树（递归）
    /**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
  bool checkSameTree(TreeNode* t1, TreeNode* t2)
  {
      // 如果两个节点指针相同，说明就是同一棵树，直接返回 true
      if(t1 == t2)
          return true;
      // 如果两个节点不同，且其中一棵为空，另一棵不为空，则两棵树肯定不同
      else if(t1 == NULL || t2 == NULL)
          return false;
      // 如果两个节点指针不同，那么要同时满足三个条件才算两棵树相同：两个节点值相同，左子树相同，右子树相同
      return t1->val == t2->val && checkSameTree(t1->left, t2->left) && checkSameTree(t1->right, t2->right);
  }
public:
  bool checkSubTree(TreeNode* t1, TreeNode* t2) {
      if(t2 == NULL)
          return true;
      if(t1 == NULL)
          return false;
      // t1和t2是同一棵树，或者t2是t1左子树的子树，或者t2是t1右子树的子树，三个条件满足其一就说明t2是t1的子树
      return checkSameTree(t1, t2) || checkSubTree(t1->left, t2) || checkSubTree(t1->right, t2);
  }
};
    执行结果： ``` 执行结果：通过

执行用时：52 ms, 在所有 C++ 提交中击败了 82.53% 的用户 内存消耗：39.4 MB, 在所有 C++ 提交中击败了 17.21% 的用户 ```