[leetcode]: 572. Subtree of Another Tree

不念不忘少年蓝@ 2022-06-15 00:11 232阅读 0赞

1.题目

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.

给定2叉树s,t.判断t是否为s的一个子树

2.分析

递归的判断
1)根结点元素值是否相同
如果相同,则判断以该节点为根结点的s的子树是否与t相同
如果不相同,则递归的判断
2)t是否为【s的左子树】的子树
3)t是否为【s的右子树】的子树

3.代码

  1. bool isSubtree(TreeNode* s, TreeNode* t) {
  2. if (s == NULL || t == NULL)
  3. return s == t;
  4. if (s->val == t->val && isSameTree(s, t))//根结点值相同则判断整棵树是否相同
  5. return true;
  6. else//否则就看s的左右子树
  7. return isSubtree(s->left, t) || isSubtree(s->right, t);
  8. }
  9. bool isSameTree(TreeNode* s, TreeNode* t) {
  10. if (s == NULL || t == NULL)
  11. return s == t;
  12. if (s->val != t->val)//same的条件是每个节点的值都相同
  13. return false;
  14. return isSameTree(s->left, t->left) && isSameTree(s->right, t->right);
  15. }

发表评论

表情:
评论列表 (有 0 条评论,232人围观)

还没有评论,来说两句吧...

相关阅读