Flowsand Cabin

Appearance

572.另一棵树的子树 ​

前言 ​

  • leetcode 572.
  • 本题用深度优先搜索暴力匹配的方法
  • 参考了 官方题解的方法一
    • 官方题解的动画拆分图做的挺形象的
  • 参考了代码随想录所讲的递归三部曲
    • 代码随想录的其它二叉树题目也有递归三部曲的讲解

整体思路 ​

这题的目的是用一颗树的子树（后续简称 rTree） 去匹配另一棵树 （后续简称 srTree）。

我们可以把这个目的拆分为两步来实现。

  1. 先在 rTree 找到一颗子树
    • 代码中我们定义为 dfs() 方法，此处我用前序遍历
  2. 把 rTree 和 srTree 比较
    • 代码中我们定义为 compare() 方法，此处我用后序遍历

代码实现 ​

java
class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        return dfs(root, subRoot);
    }
    // 1.先在 rTree 找到一颗子树
    // 1.1确定递归函数的参数和返回值
    public boolean dfs(TreeNode root, TreeNode subRoot) {
        // 1.2终止条件
        if (root == null) {
            return false;
        }
        // 1.3单层递归的代码
        if (compare(root, subRoot))
            return true;
        if (dfs(root.left, subRoot))
            return true;
        if (dfs(root.right, subRoot))
            return true;
        return false;
    }

    // 2.把 rTree 和 srTree 比较
    // 2.1确定递归函数的参数和返回值
    public boolean compare(TreeNode root, TreeNode subRoot) {
        // 2.2终止条件
        if (root == null && subRoot != null) return false;
        if (root != null && subRoot == null) return false;
        if (root == null && subRoot == null) return true;
        if (root.val != subRoot.val) return false;

        // 2.3单层递归的代码
        // 也是 if (root.val == subRoot.val) 的情况
        boolean outside = compare(root.left, subRoot.left);
        boolean inside = compare(root.right, subRoot.right);
        return outside && inside;
    }

}

我们按递归三部曲来讲解上述两步的代码实现。

先在 rTree 找到一颗子树 ​

  1. 确定递归函数的参数和返回值。

    我们让 root 在 rTree 上动，让 subRoot 不动，同时我们也要一直保存这两个 TreeNode 的信息，所以我们的 dfs 函数要有两个参数 dfs(TreeNode root, TreeNode subRoot)

    而返回值，题目需要返回 boolean，我们进行比较后，也能返回 boolean 值

  2. 确定终止条件

    if (root == null) { return false; }

    当我们的 root 遍历到 null 时，就证明当前结点以及前面遍历的结点都没匹配上，所以返回 false

  3. 单层递归的代码

java
if (compare(root, subRoot))
    return true;
if (dfs(root.left, subRoot))
    return true;
if (dfs(root.right, subRoot))
    return true;
return false;

这里我写的比官方题解更详细一点，也是为了更好的理解代码的内在逻辑。

这里我们运用的是前序遍历，对于新手来说直接看题解的简洁代码是很容易懵的。

  • return compare(root, subRoot) || dfs(root.left, subRoot) || dfs(root.right, subRoot);

我们先让 rTree 和 srTree 比较后 compare(root, subRoot)，我们再往左下移动 root ，形成新的子树和 srTree 比较 dfs(root.left, subRoot)。

把 rTree 和 srTree 比较 ​

  • 这部分建议参考代码随想录的题解 ，里面讲的更清楚，下面我做简单讲述

  1. 确定递归函数的参数和返回值。

    进行比较依然需要 root 和 subRoot 的位置信息，所以参数仍是这两个。

  2. 确定终止条件

    如果不写 if (root == null && subRoot == null) return true;会发生什么？

    面对 rTree 为 [1], srTree 为 [0] 的情况会出错。

    我们会略过终止条件后，执行单层递归的代码，最后返回真。

    把所有终止条件排除后，最后剩下 if (root.val == subRoot.val) 的情况，也就是单层递归的代码

  3. 单层递归的代码

java
boolean outside = compare(root.left, subRoot.left);
boolean inside = compare(root.right, subRoot.right);
return outside && inside;

我们先比较 rTree 和 的外侧，得出 boolean outside

再比较 rTree 和 subRoot 的内侧，得出 boolean inside

然后代码执行完，返回到父节点，进行当前 rTree 和 subRoot 整体的比较

总结 ​

这个方法很有意思的一点是：前序遍历里==套娃==了后序遍历，如此可以加深我们对二叉树遍历的理解，加强运用

前序遍历是：遍历 root，看两颗树的相同情况来决定是否继续遍历 root

后序遍历是遍历完 root 和 subRoot，比较两颗树。

几个问题 ​

使用前序遍历的好处 ​

在前序遍历的情况下，在我们从上往下遍历时，我们==先==比较上层的 root 对应的 rTree 和 srTree 是否相等，相等就可以终止递归，不继续往下遍历。这就是前序遍历的好处

为什么要提取出一个 dfs 方法 ​

其实不提出来也行，把 dfs 的名字改成 isSubtree ，把代码搬过去也是一样的。

但是呢，dfs 这个方法名更能概括我们做的事：让 root 做深度优先遍历。而 isSubtree 完全体现不出来我们要做什么

Copyright© 2024-present flowsand