LeetCode刷题二叉树——另一棵树的子树

Han.miracle

发布于 2025-12-22 14:24:11

410

文章被收录于专栏：Java核心技术图谱：原理·对比·避坑Java核心技术图谱：原理·对比·避坑

另一棵树的子树

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

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

LeetCode地址：https://leetcode.cn/problems/subtree-of-another-tree/

/**
 * 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) {
            return false;
        }
        if(isStrp(root,subRoot)){
            return true;
        }
      return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }
    public boolean isStrp(TreeNode root,TreeNode subRoot ) {
        if(root == null && subRoot == null){
            return true;
        }
        if((root != null && subRoot == null) || (root == null && subRoot != null)) {
            return false;
        }
        //根节点相同
        if(root.val != subRoot.val){
            return false;
        }
        return isStrp(root.left,subRoot.left) && isStrp(root.right,subRoot.right);
    }
}

这是博主写的，博主利用一个方法该方法也是力扣里面博主做过的题，写出来的地址是：https://leetcode.cn/problems/same-tree/

详情见上面一个作品， https://blog.csdn.net/HANhylyxy/article/details/152732396?spm=1001.2014.3001.5501

核心目标 判断两棵树 p 和 q 是否完全相同，即：

结构完全一致（节点的左右子树分布相同）；
对应位置的节点值完全相等。见以上链接 关键思想
递归的自底向上：从根节点开始，逐层深入到叶子节点，先判断最底层的子树是否相同，再向上汇总结果。
全量比较：必须确保每一个节点的存在性和值都对应相等，任何一处不匹配则整体不相同。

这是博主问Ai 的答案，思路差不多但是AI的写出来感觉不一样，多写出来一种方法不一样感觉。

/**
 * 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) {
            return false;
        }
        if (isSameTree(root, subRoot)) {
            return true;
        }
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    private boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        //|| 这个先看左边，如果是就不需要看右边了，但是她的意思仍然是null的值
        //（左边为真则不执行右边）
        if (p == null || q == null) {
            return false;
        }
        if (p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

方法思路辅助函数 isSameTree：用于判断两棵树是否完全相同。通过递归比较两棵树的对应节点：