【LeetCode】剑指 Offer 26. 树的子结构

【LeetCode】剑指 Offer 26. 树的子结构,第1张

【LeetCode】剑指 Offer 26. 树的子结构 【LeetCode】剑指 Offer 26. 树的子结构

文章目录
  • 【LeetCode】剑指 Offer 26. 树的子结构


package offer;

//定义树节点
class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(){};

    TreeNode(int x){
        val = x;
    }
}

public class Solution26 {
    public static void main(String[] args) {
        TreeNode A = new TreeNode(3);
        A.left = new TreeNode(4);
        A.right = new TreeNode(5);
        A.left.left = new TreeNode(1);
        A.left.right = new TreeNode(2);
        TreeNode B = new TreeNode(4);
        B.left = new TreeNode(1);
        Solution26 solution = new Solution26();
        System.out.println(solution.method(A, B));
    }

    public boolean method(TreeNode A, TreeNode B){
        return (A != null && B != null) && (recur(A, B) || method(A.left, B) || method(A.right, B));
    }

    //递归判断 B 是否为 A 的子树
    private boolean recur(TreeNode A, TreeNode B){
        if(B == null) return true;
        if(A == null) return false;
        if(A.val != B.val) return false;
        return recur(A.left, B.left) && recur(A.right, B.right);
    }
}

//时间复杂度为 O(n^2)
//空间复杂度为 O(n),最大递归深度为 n

欢迎分享,转载请注明来源:内存溢出

原文地址: https://outofmemory.cn/zaji/5693038.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存