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->val相等的时候就会判断不出来，就，很难受。。。
然后干脆直接写循环吧。。。行吧。。。
/** * 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 { public: bool isSubtree(TreeNode* s, TreeNode* t) { if (s == NULL && t != NULL) return false; if (solve(s, t)) return true; return isSubtree(s->left, t) || isSubtree(s->right, t); } bool solve(TreeNode* s, TreeNode* t) { if (s == NULL && t == NULL) return true; if (s == NULL || t == NULL) return false; if (s->val != t->val) return false; return solve(s->left, t->left) && solve(s->right, t->right); } }; 赋上WA代码 /** * 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 { public: bool isSubtree(TreeNode* s, TreeNode* t) { if (t == NULL) return true; if (s == NULL) return false; TreeNode* s1 = s; stack<TreeNode*> sta; sta.push(s); while (true && !sta.empty()) { TreeNode* cur = sta.top(); sta.pop(); if (cur->val == t->val) { s = cur; break; } if (cur->left) sta.push(cur->left); if (cur->right) sta.push(cur->right); } bool ans = solve(s, t); return ans; } bool solve(TreeNode* s, TreeNode* t) { if (s == NULL && t == NULL) return true; if (s == NULL || t == NULL) return false; if (s->val != t->val) return false; return solve(s->left, t->left) && solve(s->right, t->right); } };