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.
C Solution:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool isChildtree(struct TreeNode *s, struct TreeNode *t) {
if (!s && !t) return true;
if (s && t && s->val == t->val && isChildtree(s->left, t->left) && isChildtree(s->right, t->right)) return true;
return false;
}
bool isSubtree(struct TreeNode* s, struct TreeNode* t) {
if (!s && !t) return true;
if (!s || !t) return false;
if (s->val == t->val && isChildtree(s->left, t->left) && isChildtree(s->right, t->right)) return true;
if (isSubtree(s->left, t) || isSubtree(s->right, t)) return true;
return false;
}
OR
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool isSame(struct TreeNode *s, struct TreeNode *t) {
if (!t && !s) return true;
if (!t ^ !s) return false;
if (s->val != t->val) return false;
return isSame(s->left, t->left) && isSame(s->right, t->right);
}
bool isSubtree(struct TreeNode* s, struct TreeNode* t) {
if (!t) return true;
if (!s) return false;
if (isSame(s, t)) return true;
return isSubtree(s->left, t) || isSubtree(s->right, t);
}
Python Solution:
class Solution:
def isSubtree(self, s, t):
"""
:type s: TreeNode
:type t: TreeNode
:rtype: bool
"""
def preorder(s):
if not s: return ":"
return ":" + str(s.val) + ':' + preorder(s.left) + ':' + preorder(s.right) + ':'
return preorder(t) in preorder(s)
Summary:
- pre,post,in.
LeetCode: 572. Subtree of Another Tree
近期评论