剑指 Offer 26. 树的子结构

RainsX 2021-09-02 原文

剑指 Offer 26. 树的子结构

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

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

例如:
给定的树 A:

给定的树 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

限制：

0 <= 节点个数 <= 10000

算法思路：

isSubStructure(A, B) 函数：

如果A为空或者B为空，则返回false；
recur(A,B)如果B是A的子树，则返回true，否则看
- isSubStructure(A.left, B)的A的左子树是B的子树
- 或者isSubStructure(A.right, B)的A的右子树是B的子树

recur(A, B) 函数：

当节点B为空，说明B已经被匹配过了，则返回true
当A为空说明越过了A的树的子节点或者A的值不等于B的值，则返回false
返回值看recur(A.left,B.left)判断A和B的左子节点是否相等，返回则为true
看recur(A.left, B.left)判断A和B的右子节点是否相等，返回则为true

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) 
            return false;
        return recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }
    boolean recur(TreeNode A, TreeNode B) {
        if (B == null) 
            return true;
        if (A == null || A.val != B.val) 
            return false;
        return recur(A.left,B.left) && recur(A.left, B.left);
    }
}

k神的代码更为简洁，见代码如下：

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
    }
    boolean recur(TreeNode A, TreeNode B) {
        if(B == null) return true;
        if(A == null || A.val != B.val) return false;
        return recur(A.left, B.left) && recur(A.right, B.right);
    }
}

以及力友分享的注释版本：

class Solution {
    //参考视频讲解：https://www.bilibili.com/video/BV1pK4y177jA?from=search&seid=7308257970624224318
    public boolean isSubStructure(TreeNode A, TreeNode B) {
      if(A==null || B==null) return false;//约定空树不是任意一个树的子结构
      if(helper(A,B)) return true;
      return isSubStructure(A.left,B) || isSubStructure(A.right,B);//递归判断A树所有子树是否包含B树
    }
    //该函数的作用是：判断A树根节点值和B树根节点值是否相等，若不等，返回false，若相等在递归判断A树的孩子节点和B树的的孩子节点是否对应相等，如果对应相等了，就说明A的子结构包含B树，返回true。否者就不包含，返回false
    public boolean helper(TreeNode A,TreeNode B){
        if(B==null) return true;
        if(A==null || A.val!=B.val) return false;//A树为空或者A节点的值不等于B结点的值，返回false
        return helper(A.left,B.left) && helper(A.right,B.right);//当A.val==B.val时，递归判断A树的子节点和B树的子节点是否对应相等
    }
}