Python树的子结构
多出需要判断指针是不是None,避免访问空指针而造成程序崩溃。
- '''
- 输入两棵二叉树A,B,判断B是不是A的子结构
- 空树不是任意一个树的子结构
- '''
-
-
- class TreeNode:
- def __init__(self, x):
- self.val = x
- self.left = None
- self.right = None
- class Solution:
- def HasSubtree(self, pRoot1, pRoot2):
- result = False
- if pRoot1 != None and pRoot2 != None:
- if pRoot1.val == pRoot2.val:
- result = self.DoesTree1haveTree2(pRoot1, pRoot2)
- if not result:
- result = self.HasSubtree(pRoot1.left, pRoot2)
- if not result:
- result = self.HasSubtree(pRoot1.right, pRoot2)
- return result
- # 用于递归判断树的每个节点是否相同
- # 需要注意的地方是: 前两个if语句不可以颠倒顺序
- # 如果颠倒顺序, 会先判断pRoot1是否为None, 其实这个时候pRoot2的结点已经遍历完成确定相等了, 但是返回了False, 判断错误
- def DoesTree1haveTree2(self, pRoot1, pRoot2):
- if pRoot2 == None:
- return True
- if pRoot1 == None:
- return False
- if pRoot1.val != pRoot2.val:
- return False
-
- return self.DoesTree1haveTree2(pRoot1.left, pRoot2.left) and self.DoesTree1haveTree2(pRoot1.right, pRoot2.right)
-
- pRoot1 = TreeNode(8)
- pRoot2 = TreeNode(8)
- pRoot3 = TreeNode(7)
- pRoot4 = TreeNode(9)
- pRoot5 = TreeNode(2)
- pRoot6 = TreeNode(4)
- pRoot7 = TreeNode(7)
- pRoot1.left = pRoot2
- pRoot1.right = pRoot3
- pRoot2.left = pRoot4
- pRoot2.right = pRoot5
- pRoot5.left = pRoot6
- pRoot5.right = pRoot7
-
- pRoot8 = TreeNode(8)
- pRoot9 = TreeNode(9)
- pRoot10 = TreeNode(2)
- pRoot8.left = pRoot9
- pRoot8.right = pRoot10
-
- S = Solution()
- print(S.HasSubtree(pRoot1, pRoot8))
解压密码: detechn或detechn.com
免责声明
本站所有资源出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。
本站发布资源来源于互联网,可能存在水印或者引流等信息,请用户自行鉴别,做一个有主见和判断力的用户。
本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。