( “树” 之 DFS) 572. 另一棵树的子树 ——【Leetcode每日一题】

港控/mmm° 2024-03-23 11:43 64阅读 0赞

### 572. 另一棵树的子树 ###

给你两棵二叉树 `root` 和 `subRoot` 。检验 `root` 中是否包含和 `subRoot` 具有相同结构和节点值的子树。如果存在，返回 `true` ；否则，返回 `false` 。

二叉树 `tree` 的一棵子树包括 `tree` 的某个节点和这个节点的所有后代节点。`tree` 也可以看做它自身的一棵子树。

##### 示例 1： #####

![在这里插入图片描述][650a3f4ecbe94a97b0f2c3118f4ab09a.png]

> 输入：root = \[3,4,5,1,2\], subRoot = \[4,1,2\]  
> 输出：true

##### 示例 2： #####

![在这里插入图片描述][052e80c7cc4b4f448aba384cfeb89d10.png]

> 输入：root = \[3,4,5,1,2,null,null,null,null,0\], subRoot = \[4,1,2\]  
> 输出：false

**提示：**

*  `root` 树上的节点数量范围是 \[1, 2000\]
 *  `subRoot` 树上的节点数量范围是 \[1, 1000\]
 *   − 1 0 4 < = r o o t . v a l < = 1 0 4 -10^4 <= root.val <= 10^4 −104<=root.val<=104
 *   − 1 0 4 < = s u b R o o t . v a l < = 1 0 4 -10^4 <= subRoot.val <= 10^4 −104<=subRoot.val<=104

#### 思路：DFS ####

首先任意看一个节点的`root.val`，该节点可能等于`subRoot.val`，也可能不相等，共有两种可能，对应的也就有两种不同的操作：

*  当`root.val` == `subRoot.val`时，则判断剩余的后代节点是否都相等，如果有其中一个不相等，则`subRoot`不是`root`的子树，返回`false`，如果走到叶子节点都相等的话返回`true`;
 *  当`root.val` != `subRoot.val`时, 则接着到`root`的左右节点比较，只要有其中一个满足子树，就返回`true`;
 *  递归上述两种情况则可判断是否存在子树。

#### 代码：(Java、C++) ####

**Java**

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        
            if(root == null || subRoot == null) {
        
                return false; 
            }
            return dfs(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
        }
        public boolean dfs(TreeNode root, TreeNode subRoot) {
        
            if(root == null && subRoot == null) return true;
            if(root == null || subRoot == null || root.val != subRoot.val){
        
                return false;
            } 
            return dfs(root.left, subRoot.left) && dfs(root.right, subRoot.right);
        }
    }

**C++**

/**
     * 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* root, TreeNode* subRoot) {
        
            if(root == NULL || subRoot == NULL) {
        
                return false; 
            }
            return dfs(root, subRoot) || isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
        }
        bool dfs(TreeNode* root, TreeNode* subRoot) {
        
            if(root == NULL && subRoot == NULL) return true;
            if(root == NULL || subRoot == NULL || root->val != subRoot->val){
        
                return false;
            } 
            return dfs(root->left, subRoot->left) && dfs(root->right, subRoot->right);
        }
    };

##### 运行结果： #####

![在这里插入图片描述][1285cec7f5ad4a339ccd0f313c067508.png]

##### 复杂度分析： #####

*  **时间复杂度**： O ( n ∗ m ) O(n\*m) O(n∗m)，`m`为`root`的节点数，`n`为`subRoot`的节点数，对于每一个`root`上的点，都需要做一次深度优先搜索来和`subRoot`匹配，匹配一次的时间代价是  O ( m ) O(m) O(m)。
 *  **空间复杂度**： O ( n ) O(n) O(n)，考虑到递归需要在栈上开辟空间，最大深度为`n`。

题目来源：[力扣。][Link 1]

> 放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！  
> 关注我 [leetCode专栏][leetCode]，每日更新！

##### 注： 如有不足，欢迎指正！ #####

[650a3f4ecbe94a97b0f2c3118f4ab09a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/37f8cf828dcc444bb6dcdddeedf35e77.png
[052e80c7cc4b4f448aba384cfeb89d10.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/9e1751a80cee4f4b889a8b593b9a12ee.png
[1285cec7f5ad4a339ccd0f313c067508.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/61d6768634e4433f9e83b954366ec8b0.png
[Link 1]: https://leetcode.cn/problems/subtree-of-another-tree/description/?orderBy=most_votes%3ForderBy%3Dmost_votes%3ForderBy%3Dmost_votes%3ForderBy%3Dmost_votes
[leetCode]: http://t.csdn.cn/kQLJO