LeetCode Subtree of Another Tree Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself. Example 1: Given tree s:

     3
    / \
   4   5
  / \
 1   2

Given tree t:

   4
  / \
 1   2

Return true, because t has the same structure and node values with a subtree of s. Example 2: Given tree s:

     3
    / \
   4   5
  / \
 1   2
    /
   0

Given tree t:

   4
  / \
 1   2

Return false.

---

判断二叉树t是否是二叉树s的子树。如果t是s从node0开始的子树，则t必须和node0子树完全一样，node0不能有多余的孩子，比如样例2中node0的子树多有一个节点0，所以是False。 首先写一个子程序check判断子树s和t是否相等，然后在主程序中使用先序遍历s，如果发现s的某个节点node0的值和t的根节点相等，则可以进入check(node0,t)判断node0子树是否和t相等。 代码如下： [cpp] class Solution { private: bool check(TreeNode* s, TreeNode* t) { if ((s == NULL && t != NULL) || (s != NULL&&t == NULL))return false; if (s == NULL && t == NULL)return true; //s!=NULL&&t!=NULL return (s->val == t->val) && check(s->left, t->left) && check(s->right, t->right); } public: bool isSubtree(TreeNode* s, TreeNode* t) { if (t == NULL)return true; if (s == NULL)return false; queue<TreeNode*> q; q.push(s); while (!q.empty()) { TreeNode *tmp = q.front(); q.pop(); if (tmp->val == t->val) { if (check(tmp, t))return true; } if (tmp->left != NULL)q.push(tmp->left); if (tmp->right != NULL)q.push(tmp->right); } return false; } }; [/cpp] 本代码提交AC，用时29MS。 还有一种更简洁漂亮的解法。如果t是s的子树，有三种情况，t要么和s完全相等check(s,t)，要么等于s的某个左子树isSubtree(s->left,t)，要么等于s的某个右子树isSubtree(s->right,t)。所以主程序和子程序都可以递归。 代码如下： [cpp] class Solution { private: bool check(TreeNode* s, TreeNode* t) { if ((s == NULL && t != NULL) || (s != NULL&&t == NULL))return false; if (s == NULL && t == NULL)return true; //s!=NULL&&t!=NULL return (s->val == t->val) && check(s->left, t->left) && check(s->right, t->right); } public: bool isSubtree(TreeNode* s, TreeNode* t) { if (t == NULL)return true; if (s == NULL)return false; if (check(s, t))return true; return isSubtree(s->left, t) || isSubtree(s->right, t); } }; [/cpp] 本代码提交AC，用时32MS。]]>