LCR 143. 子结构判断

代码与解析

这是我一开始的代码，只过了45/49个测试用例，在测试用例这过不了了，不知道为啥

输入:

A =[-2,1,-1]

B =[-2,1,1]

输出

true

预期结果

false

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        return dfs(A,B);
    }
    public boolean dfs(TreeNode node1, TreeNode node2) {
        if(node1 == null || node2 == null)   return false;
        if(node1.left == null && node1.right == null && node2.left == null && node2.right == null)  return true;
        if(node1.val != node2.val) {
            return dfs(node1.left, node2) ||
            dfs(node1.right, node2);
        }
        return dfs(node1.left, node2.left) && dfs(node1.right, node2.right);
    }
}

改了好几个版本，测试用例一个个的过感觉这样子不太好，于是还是看了题解，结合题解写的代码和注释

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    /**
     * 判断树 A 是否包含树 B 的子结构
     *
     * @param A 二叉树 A 的根节点
     * @param B 二叉树 B 的根节点
     * @return 如果树 A 包含树 B 的子结构返回 true，否则返回 false
     */
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        // 判断 A 和 B 非空，若任一为空，则返回 false
        return ((A != null && B != null) &&
                // 以 A 和 B 为根节点的子树是否包含 B，或者 A 的左子树或右子树中是否包含 B 的子结构
                (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B)));
    }

    /**
     * 递归判断以 A 和 B 为根节点的子树是否相等
     *
     * @param A 二叉树 A 的子节点
     * @param B 二叉树 B 的子节点
     * @return 如果以 A 和 B 为根节点的子树相等返回 true，否则返回 false
     */
    public boolean recur(TreeNode A, TreeNode B) {
        // 当 B 为空时，说明 B 的所有节点都已匹配，返回 true
        if (B == null) return true;
        // 当 A 为空或 A 的值与 B 的值不相等时，说明不匹配，返回 false
        if (A == null || A.val != B.val) return false;
        // 递归判断 A 和 B 的左子树和右子树是否相等
        return recur(A.left, B.left) && recur(A.right, B.right);
    }
}