为什么我没有得到预期的输出？

Question

我是初学者 trees.I 定义了一个 findNode 函数到 return node.Then 我递归地检查节点作为根和子树是否是 same.But 我没有获得以下测试用例的预期输出。怎么能改呢。提前致谢

预计output:true

输入：树：[1,1]

子树：[1]

但我得到的输出是错误的

leetcode问题：https://leetcode.com/problems/subtree-of-another-tree/submissions/

    def findNode(self,root,subRoot):
        if root==None:
            return None
        if root.val==subRoot.val:
            return root
        if root.left:
            return self.findNode(root.left,subRoot)
        if root.right:
            return self.findNode(root.right,subRoot)
        
    def check(self,root,subRoot):
        if root==None and subRoot==None:
            return True
        if root==None or subRoot==None:
            return False
        if root.val!=subRoot.val:
            return False
        return self.check(root.right,subRoot.right) and self.check(root.left,subRoot.left)
    
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        node=self.findNode(root,subRoot)
        return self.check(node,subRoot)
    ```

Answer 1

您的代码中存在问题，因为一旦您找到与 subRoot 节点匹配的节点，您就会停止搜索并使用运行 check() 函数，它可以 return false 并且您的程序将 return false 而不检查可以匹配的更深的子树。这是我的代码：

class Solution:
    def findMatchingTree(self,root,subRoot):
        if root==None:
            return False
        return self.check(root, subRoot) or self.findMatchingTree(root.left,subRoot) or self.findMatchingTree(root.right,subRoot)
        
    def check(self,root,subRoot):
        if root==None and subRoot==None:
            return True
        if root==None or subRoot==None:
            return False
        if root.val!=subRoot.val:
            return False
        return self.check(root.right,subRoot.right) and self.check(root.left,subRoot.left)
    
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        return self.findMatchingTree(root,subRoot)

如果你想使代码更快，我建议你从树的叶子中搜索根。

为什么我没有得到预期的输出？

Why Am I not getting expected output?

binary-tree