使用 dfs 确定给定树是否为子树

Question

我正在尝试确定一棵树 (t) 是否是另一棵树 (s) 的子树。

这是对leetcode的link，彻底解释了问题：https://leetcode.com/problems/subtree-of-another-tree/

我的方法：我有一个函数对 s 执行 dfs 并在另一个函数中将每个节点与 t 的根进行比较以确定 t 是否是 s 的子树

我的解决方案在 s=[1,1] 和 t=[1] 时不起作用，尽管我认为它应该起作用。你能看看我的代码并解释哪里出了问题吗？

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        /* dfs on s, at each node running a compare tree function for s at that node and
        root of t*/
        
        if(s == null || t == null) {
            return false;
        }
        
        return dfs(s, t);
    }
    
    public static boolean dfs(TreeNode s, TreeNode t) {
        if(s == null) {
            return false;
        }
        
        if(s.val == t.val) {
            return isSameTree(s, t);
        }
        
        
        return dfs(s.left, t) || dfs(s.right, t);
    }
    
    public static boolean isSameTree(TreeNode s, TreeNode t) {
        if(s == null || t == null) {
            return s == t;
        }
        
        if(s.val != t.val) {
            return false;
        }
        
        return isSameTree(s.left, t.left) && isSameTree(s.right, t.right);
    }
}

Answer 1

看起来不错！快到了！

这会过去：

public class Solution {
    public static final boolean isSubtree(
        final TreeNode s,
        final TreeNode t
    ) {
        if (s == null) {
            return false;
        }

        if (checkNextLevel(s, t)) {
            return true;
        }

        return isSubtree(s.left, t) ||
               isSubtree(s.right, t);
    }

    private static final boolean checkNextLevel(
        final TreeNode s,
        final TreeNode t
    ) {
        if (s == null && t == null) {
            return true;
        }

        if (
            (s == null || t == null) ||
            (s.val != t.val)
        ) {
            return false;
        }


        return checkNextLevel(s.left, t.left) &&
               checkNextLevel(s.right, t.right);
    }
}

Answer 2

您需要检查 s 的所有节点是否 t 是该节点的子树。如果在 s 上执行 dfs 时停在第一个节点，它的值与 t 的根节点相同但子树不同，则可能存在树 s 的另一个节点，其值和子树两者都与 t.

相同

换句话说，您需要重复第一步（在 s 上执行 dfs 并将 s 的每个节点与 t 的根进行比较）直到您检查了所有s 的节点（dfs 在 s 上完成）或发现 t 是 s.

的子树

            s                        t

           (1)                      (1)
          /
       (1) 

Do not return from root of s just because of same values of root of s and t. If t is not subtree of that node, keep doing dfs to find another node whose value and subtree both are same as t (left child of root of s in this case).

为了更加清晰，下面是您的代码，其中突出显示了更正的部分：

class Solution {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        /* dfs on s, at each node running a compare tree function for s at that node and
        root of t*/
        
        if(s == null || t == null) {
            return false;
        }
        
        return dfs(s, t);
    }
    
    public static boolean dfs(TreeNode s, TreeNode t) {
        if(s == null) {
            return false;
        }
        
        // ==== Corrected below if ====
        // apart from s.val == t.val, if isSameTree(s, t) is true at this
        // point, return true; otherwise keep doing dfs for rest of the tree s
        // other same value node of s can be the answer
        if(s.val == t.val && isSameTree(s, t)) {
            return true;
        }
        
        
        return dfs(s.left, t) || dfs(s.right, t);
    }
    
    public static boolean isSameTree(TreeNode s, TreeNode t) {
        if(s == null || t == null) {
            return s == t;
        }
        
        if(s.val != t.val) {
            return false;
        }
        
        return isSameTree(s.left, t.left) && isSameTree(s.right, t.right);
    }
}