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:
Given tree s:
3 / \ 4 5 / \ 1 2Given tree t:
4 / \ 1 2Return true, because t has the same structure and node values with a subtree of s.
Example 2:
Given tree s:
Given tree s:
3 / \ 4 5 / \ 1 2 / 0Given tree t:
4 / \ 1 2
A:
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool isSubtree(TreeNode* s, TreeNode* t) { return isSame(s,t) || (s->left && isSubtree(s->left, t)) || (s->right && isSubtree(s->right, t)); } private: bool isSame(TreeNode* s, TreeNode* t){ if(not s and not t) return true; if(not s or not t) return false; return (s->val == t->val) && isSame(s->left, t->left) && isSame(s->right, t->right); } };
No comments:
Post a Comment