讨论/《画解剑指 Offer》 - 剑指 Offer 26.数的子结构 - 解题思路/
《画解剑指 Offer》 - 剑指 Offer 26.数的子结构 - 解题思路
共 12 个回复

递归真难啊

4

这题迭代好想一些,先序遍历查找A,直到找到与B根节点值相同为止,然后开始内循环对比,如果一致则直接返回,否则继续先序遍历查A剩下结点,如果有第二个与B根节值相同结点,则再进行对比。
def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
if not B:
return False
sign = False
a_stack1 = list()
a_stack1.append(A)
while a_stack1:
cur_node = a_stack1.pop()
if cur_node.val == B.val:
a_stack, b_stack = list(), list()
a_stack.append(cur_node)
b_stack.append(B)
sign = True
while b_stack and a_stack:
cur_a = a_stack.pop()
cur_b = b_stack.pop()
if cur_a.val == cur_b.val:
if cur_b.right:
if not cur_a.right:
sign = False
break
b_stack.append(cur_b.right)
a_stack.append(cur_a.right)
if cur_b.left:
if not cur_a.left:
sign = False
break
b_stack.append(cur_b.left)
a_stack.append(cur_a.left)
else:
sign = False
break
if sign:
return True
else:
sign = False
if cur_node.right:
a_stack1.append(cur_node.right)
if cur_node.left:
a_stack1.append(cur_node.left)
return False

1

优秀丫

1

打卡

1

打卡

1

题目有点小错误,不是数的子结构,而是树的子结构。有空可以更正

1

打卡

1

每次看到这种递归都不敢相信是真的

判断子结构的条件有意思。