LeetCode Algorithm 572. 另一棵树的子树

572. 另一棵树的子树

Ideas

首先想到的就是递归判断两棵树的每一个节点是否相等，那么就需要将subRoot跟root的每一个节点构成的子树判断是否相同。

递归判断相等的逻辑比较简单，首先当前两个节点值相等，然后递归判断左子树是否相等，再递归判断右子树是否相等。

递归的终止条件，就是两棵树同时到达了叶子结点，并且都没有孩子节点，此时说明这两颗子树相等。

再具体一点，我们首先要判断subRoot是不是root的子树，有三种情况：

subRoot和root两棵树相等；

subRoot是root的左子树；

subRoot是root的右子树。

然后我们要判断subRoot和root是不是相等，需要满足三个条件：

当前两棵树的根节点相等；

subRoot的左子树和root的左子树相等；

subRoot的右子树和root的右子树相等；

所以这里有两个递归的过程，我们需要再定义一个辅助函数。

Code

Python

# Definition for a binary tree node. class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightclass Solution:def isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:if not root and not subRoot:return Trueif not root or not subRoot:return Falsereturn self.isSameTree(root, subRoot) or self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)def isSameTree(self, root: TreeNode, subRoot: TreeNode):if not root and not subRoot:return Trueif not root or not subRoot:return Falsereturn root.val == subRoot.val and self.isSameTree(root.left, subRoot.left) and self.isSameTree(root.right, subRoot.right)

总结

以上是生活随笔为你收集整理的LeetCode Algorithm 572. 另一棵树的子树的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。