Problem
题目大意：判断一棵树是不是另外一棵树的子树。
https://leetcode.com/problems/subtree-of-another-tree/description/
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:
|
1 2 3 4 5 |
3 / \ 4 5 / \ 1 2 |
Given tree t:
|
1 2 3 |
4 / \ 1 2 |
Return true, because t has the same structure and node values with a subtree of s.
Example 2:
Given tree s:
|
1 2 3 4 5 6 7 |
3 / \ 4 5 / \ 1 2 / 0 |
Given tree t:
|
1 2 3 |
4 / \ 1 2 |
Return false.
Solution: Recursion
Time complexity: O(max(n, m))
Space complexity: O(max(n, m))
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua // Running time: 29 ms class Solution { public: bool isSubtree(TreeNode* s, TreeNode* t) { if (t == nullptr) return true; if (s == nullptr) return false; if (isSameTree(s, t)) return true; return isSubtree(s->left, t) || isSubtree(s->right, t); } private: bool isSameTree(TreeNode* s, TreeNode* t) { if (s == nullptr && t == nullptr) return true; if (s == nullptr || t == nullptr) return false; return (s->val == t->val) && isSameTree(s->left, t->left) && isSameTree(s->right, t->right); } }; |
Related Problems
- [解题报告] Leetcode 100. Same Tree
- 花花酱 LeetCode 508. Most Frequent Subtree Sum
- 花花酱 LeetCode 563. Binary Tree Tilt
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment