剑指 Offer 26: 树的子结构

[songyy5517]

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

例如: 给定的树 A:

     3

    / \

   4   5

  / \

 1   2

给定的树 B：

   4 

  /

 1

返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：

输入：A = [1,2,3], B = [3,1]
输出：false

示例 2：

输入：A = [3,4,5,1,2], B = [4,1]
输出：true

分析 这道题需要我们判断树B是否为树B的子结构。一个很直接的想法是，先遍历树A，找到与树B根节点值相同的节点，然后依次比较两棵子树是否相等。其中关键点是如何比较子树。 我们可以定义一个Boolean类型的递归方法，判断节点A和节点B所在子树是否匹配。若两个节点值相等，则继续对其左右子树进行递归判断。

[songyy5517]

思路: 遍历 & 递归比较左右子树

1. 特殊值处理/递归出口；
2. 先根递归遍历A树，判断A的当前节点是否与B的根节点值相等（可以在主方法中递归实现）； (1) 若相等，则判断以B为根节点的树是否为以A为根节点树的子结构；(定义一个新的递归方法 isSubTree) (2) 若不是子结构，则递归遍历A剩下的节点。
3. 返回结果；

boolean isSubTree(A, B)：判断以A为根节点的子树是否包含以B为根节点的子树

1. 特殊值处理/递归出口： （1）若B为空，则说明B中的所有节点匹配成功，返回true； （2）若A为空，此时B不为空，则说明匹配失败，返回false。
2. 比较节点的值： (1) 若相等，则继续比较其左右子节点； (2) 若不相等，则返回false。

复杂度分析：

• 时间复杂度： $O(MN)$ ，其中M, N分别为二叉树A和B的节点数量，遍历二叉树A需要 $O(M)$ ；若节点值相同，则需要继续调用递归函数 isSubTree，对二叉树B中的各个节点进行比较，需要 $O(N)$ ，因此总时间复杂度为 $O(MN)$ 。
• 空间复杂度： $O(M)$ ，（最坏情况下）当二叉树A和B都退化成链表时，递归深度最大。若 $M>N$ ，则需要遍历到A的叶子节点，深度为M；若 $M<=N$ ，则需要遍历完A，深度也为M。

[songyy5517]

/**
 * 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) {
        // 1. 特殊值处理/递归出口
        if (A == null || B == null)
            return false;

        // 2. 递归判断：遍历树A，比较A当前节点和B根节点
        boolean res = false;

        // 2.1 若两节点值相等，则判断B树是否在以该节点为根节点的子树中 (isSubTree)
        if (A.val == B.val){
            res = isSubTree(A, B);
        }

        // 2.2 若不相等，则继续遍历A的剩余节点
        // 此处不能else，因为之后的遍历过程中，还可能会出现与B节点值相同的节点 （2023/2/13）
        if (!res)
            return isSubStructure(A.left, B) || isSubStructure(A.right, B);

        return res;
    }

    // 作用：递归判断以B为根节点的树是否为以A为根节点树的子结构
    public static boolean isSubTree(TreeNode A, TreeNode B){
        // 递归出口
        if (B == null)
            return true;

        if (A == null)     // 此时A为空，B不为空，说明匹配失败（2023/2/13）
            return false;

        if (A.val == B.val)
            return isSubTree(A.left, B.left) && isSubTree(A.right, B.right);  // 这里是&&，两个条件必须同时满足
        else
            return false;
    }
}

[songyy5517]

2023/2/13

1. 若节点值匹配，而以当前节点为根的子树不包含子结构，则需要继续遍历剩下的节点（if (!res)）
2. 在判断以当前节点为根的子树是否为子结构的函数（isSubTree）中，匹配失败的递归出口为：root1为空，且应放在匹配成功的出口后（root2为空）
3. 二叉树递归遍历函数可以用主函数（isSubStructure）实现，无需另外定义函数（当然也可以）

2024/1/22

1. 树A可以不为空，如果树B为空则说明匹配成功了。
2. 可以将递归方法整合到主方法中的条件：形参一致，逻辑一致。
3. boolean变量定义的位置。（2024/2/26）