LeetCode-572. 另一棵树的子树

柔情只为你懂 2024-03-27 15:55 98阅读 0赞

题目来源  
[572. 另一棵树的子树][572.]

### 解题思路 ###

看到题目描述，首先判断一个树是否是另一棵树的子树，很明显想到可以用递归，但是两棵树完全相同也可以看做一棵树是另一棵树的子树。 所以自然而然想到用一个判断两棵树是否相同的递归函数。

class Solution {
        
        public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        
            if (subRoot == null) return true;   // subRoot 为 null 一定都是 true
            if (root == null) return false;  // 这里 subRoot 一定不为 null, 只要 root 为 null，肯定是false
            return isSameTree(root,subRoot) || isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
        }
    
        public static boolean isSameTree(TreeNode root, TreeNode subRoot){
        
            if(root == null && subRoot == null){
        
                return true;
            }
            if(root == null || subRoot == null){
        
                return false;
            }
            if(root.val != subRoot.val){
        
                return false;
            }
            return isSameTree(root.left,subRoot.left) && isSameTree(root.right,subRoot.right);
        }
    
    }

![在这里插入图片描述][87a60ac264b544108fb5703acd82d56f.png]  
这道题解决了，可以去做下下面的两道题，只需要修改一下代码就可以了  
[LeetCode-101. 对称二叉树][LeetCode-101.]  
[LeetCode-100. 相同的树][LeetCode-100.]

[572.]: https://leetcode.cn/problems/subtree-of-another-tree/
[87a60ac264b544108fb5703acd82d56f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/23f0215a60d2430fa1194338b75dd4a8.png
[LeetCode-101.]: https://donglin.blog.csdn.net/article/details/128969588
[LeetCode-100.]: https://donglin.blog.csdn.net/article/details/128985423