java - 使用 dfs 确定给定树是否是子树

问题描述

我试图确定一棵树（t）是否是另一棵树（s）的子树。

这是 leetcode 的链接，它彻底解释了问题：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);
    }
}

标签： javatreebinary-treetree-traversal

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

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

            s                        t

           (1)                      (1)
          /
       (1) 
不要因为 s 和 t 的根值相同而从 s 的根返回。如果 t 不是该节点的子树，则继续执行 dfs 以找到另一个值和子树都与 t 相同的节点（在这种情况下为 s 的根的左子节点）。

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

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);
    }
}

java - 使用 dfs 确定给定树是否是子树

问题描述

解决方案

推荐阅读