日期: 2024 年 8 月 4 日

572.另一棵树的子树

目标

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

示例 1：

输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true

示例 2：

输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false

说明：

  • root 树上的节点数量范围是 [1, 2000]
  • subRoot 树上的节点数量范围是 [1, 1000]
  • -10^4 <= root.val <= 10^4
  • -10^4 <= subRoot.val <= 10^4

思路

判断给定的树是否是另一颗树的子树。

刚开始想以某种顺序（先/中/后）遍历给定的树并记录访问节点，然后遍历另一棵树，如果节点值等于给定树的根节点则以同样的顺序记录其子树，再比较记录是否相同。但是这并不能保证结构是相同的。

只能逐个节点比较。进一步优化可以计算树的高度，只比较高度相同的。//todo

看了官网题解可以引入两个null值，进行串匹配的时候可以使用 KMP 或者 Rabin-Karp 算法。//todo

也提供了将树映射为hash值来比较的思路。//todo

代码

/**
 * @date 2024-08-04 15:36
 */
public class IsSubtree572 {

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return false;
        }
        if (root.val == subRoot.val) {
            if (compare(root, subRoot)) {
                return true;
            }
        }
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    public boolean compare(TreeNode root, TreeNode subRoot) {
        if (root.val != subRoot.val) {
            return false;
        }
        boolean res = false;
        if (root.left != null && subRoot.left != null) {
            res = compare(root.left, subRoot.left);
        } else if (root.left == null && subRoot.left == null){
            res = true;
        }
        if (root.right != null && subRoot.right != null) {
            res = compare(root.right, subRoot.right) && res;
        } else if (root.right == null && subRoot.right == null) {
        } else {
            res = false;
        }
        return res;
    }

}

性能