难度:Easy
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 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:3/ \4 5/ \1 2/0Given tree t:4/ \1 2Return false.
需要子树的要求,在子树到达叶子节点的时候,原数也是叶子节点。
/*** 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 {bool isEqual(TreeNode*s,TreeNode*t){if(!t) return s? false :true;if(!s) return false;if(s->val != t->val) return false;return isEqual(s->left,t->left) && isEqual(s->right,t->right);}public:bool isSubtree(TreeNode* s, TreeNode* t) {if(!s && !t) return true;if(!s || !t) return false;if(s->val == t->val && isEqual(s,t)) return true;return isSubtree(s->left,t) || isSubtree(s->right,t);}};
执行用时 :36 ms, 在所有 C++ 提交中击败了86.12%的用户 内存消耗 :21 MB, 在所有 C++ 提交中击败了77.88%的用户