[leetcode]: 572. Subtree of Another Tree

不念不忘少年蓝@ 2022-06-15 00:11 147阅读 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.代码 #

bool isSubtree(TreeNode* s, TreeNode* t) {
        if (s == NULL || t == NULL)
            return s == t;
        if (s->val == t->val && isSameTree(s, t))//根结点值相同则判断整棵树是否相同
            return true;
        else//否则就看s的左右子树
            return isSubtree(s->left, t) || isSubtree(s->right, t);
    }
    bool isSameTree(TreeNode* s, TreeNode* t) {
        if (s == NULL || t == NULL)
            return s == t;
        if (s->val != t->val)//same的条件是每个节点的值都相同
            return false;
        return isSameTree(s->left, t->left) && isSameTree(s->right, t->right);
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，147人围观）

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

相关阅读

相关 LeetCode - Easy - 572. Subtree of Another Tree

Topic Tree Description [https://leetcode.com/problems/subtree-of-another-tree/

布满荆棘的人生/ 2022年10月15日 00:37/ 0 赞/ 2 阅读

相关【Leetcode】543. Diameter of Binary Tree

思路：定义一个类变量diameter，保存最大diameter值。通过递归计算左右子树的深度来计算根节点的diameter（记为temp），通过和类变量 diamete

Myth丶恋晨/ 2022年09月30日 07:28/ 0 赞/ 138 阅读

相关 LeetCode-Maximum Depth of Binary Tree

Problem: > > Given a binary tree, find its maximum depth. > > > The maximum depth i

Bertha 。/ 2022年08月09日 03:14/ 0 赞/ 4 阅读

相关 [leetcode]-543. Diameter of Binary Tree

![Center][] 思路： diameter保存最大的直径，每次更新该值 depthOfBinary利用分治算法计算树的深度：分解为子问题，分别求得左右子树的深度lD

比眉伴天荒/ 2022年06月18日 01:09/ 0 赞/ 146 阅读

相关 [leetcode]: 572. Subtree of Another Tree

1.题目 Given two non-empty binary trees s and t, check whether tree t has exactly the s

不念不忘少年蓝@/ 2022年06月15日 00:11/ 0 赞/ 148 阅读

相关 [leetcode]: 543. Diameter of Binary Tree

1.题目 Given a binary tree, you need to compute the length of the diameter of the tree.

骑猪看日落/ 2022年06月15日 00:10/ 0 赞/ 203 阅读

相关 LeetCode543. Diameter of Binary Tree

Solution1 If we think about it, there may be three conditions for the largest diamete

小鱼儿/ 2022年06月07日 03:37/ 0 赞/ 143 阅读

相关 leetcode 572. Subtree of Another Tree 子树判断 + 深度优先遍历DFS

Given two non-empty binary trees s and t, check whether tree t has exactly the same stru

客官°小女子只卖身不卖艺/ 2022年06月03日 04:23/ 0 赞/ 148 阅读

相关 LeetCode：572. Subtree of Another Tree（判断一棵树是不是另外一棵树的子树）

> 文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如

- 日理万妓/ 2022年04月11日 13:53/ 0 赞/ 200 阅读

相关 Maximum Depth of Binary Tree leetcode

Given a binary tree, find its maximum depth. The maximum depth is the number of nodes a

Bertha 。/ 2022年01月09日 23:11/ 0 赞/ 311 阅读