@TOC
1. 题目概述
题目抽象：给2棵树A，树B，判断B是否是A的子结构。 子结构定义：树A和树B的根结点相等，并且树A的左子树和树B的左子树相等，树A的右子树和树B的右子树相等
2. 解题思路
3. 算法流程
名词规定：树 AA 的根节点记作 节点 AA ，树 BB 的根节点称为 节点 BB 。
以上 2. 3. 实质上是在对树 AA 做 先序遍历 。
4. 复杂度分析：
5. 代码实现
5.1 Java实现
class Solution {
public boolean isSubStructure(TreeNode A
, TreeNode B
) {
return (A
!= null
&& B
!= null
) && (recur(A
, B
) || isSubStructure(A
.left
, B
) || isSubStructure(A
.right
, B
));
}
boolean recur(TreeNode A
, TreeNode B
) {
if(B
== null
) return true;
if(A
== null
|| A
.val
!= B
.val
) return false;
return recur(A
.left
, B
.left
) && recur(A
.right
, B
.right
);
}
}
5.3 Python实现
class Solution:
def isSubStructure(self
, A
: TreeNode
, B
: TreeNode
) -> bool:
def recur(A
, B
):
if not B
: return True
if not A
or A
.val
!= B
.val
: return False
return recur
(A
.left
, B
.left
) and recur
(A
.right
, B
.right
)
return bool(A
and B
) and (recur
(A
, B
) or self
.isSubStructure
(A
.left
, B
) or self
.isSubStructure
(A
.right
, B
))
作者：jyd 链接：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/solution/mian-shi-ti-26-shu-de-zi-jie-gou-xian-xu-bian-li-p/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
