【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