本文主要是介绍剑指offer：输入两棵二叉树A，B，判断B是不是A的子结构（Python），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
解题思路
我的弯路
分别获取A和B的前序遍历数组和中序遍历数组——> 比较B的前序遍历数组是否按序在A的前序遍历数组中；比较B的中序遍历数组是否按序在A的中序遍历数组中；
正确思路
遍历二叉树A，定位B的根节点在A中的可能位置——> 定位后，验证B是不是A当前位置的子结构。
Python代码
class Solution:# 给定两个二叉树（的根节点）A、B，判断B 是不是A 的二叉树def HasSubtree(self, pRoot1, pRoot2):if pRoot1 == None or pRoot2 == None:return Falseresult = Falseif pRoot1.val == pRoot2.val:result = self.isSubtree(pRoot1, pRoot2)if result == False:result = self.HasSubtree(pRoot1.left, pRoot2) | self.HasSubtree(pRoot1.right, pRoot2)return resultdef isSubtree(self, root1, root2):if root2 == None:return Trueif root1 == None:return Falseif root1.val == root2.val:return self.isSubtree(root1.left, root2.left) & self.isSubtree(root1.right, root2.right)return False包含测试数据完整Python代码如下：
class Solution:# 给定两个二叉树（的根节点）A、B，判断B 是不是A 的二叉树def HasSubtree(self, pRoot1, pRoot2):if pRoot1 == None or pRoot2 == None:return Falseresult = Falseif pRoot1.val == pRoot2.val:result = self.isSubtree(pRoot1, pRoot2)if result == False:result = self.HasSubtree(pRoot1.left, pRoot2) | self.HasSubtree(pRoot1.right, pRoot2)return resultdef isSubtree(self, root1, root2):if root2 == None:return Trueif root1 == None:return Falseif root1.val == root2.val:return self.isSubtree(root1.left, root2.left) & self.isSubtree(root1.right, root2.right)return False# 给定二叉树的前序遍历和中序遍历，获得该二叉树def getBSTwithPreTin(self, pre, tin):if len(pre)==0 | len(tin)==0:return Noneroot = treeNode(pre[0])for order,item in enumerate(tin):if root .val == item:root.left = self.getBSTwithPreTin(pre[1:order+1], tin[:order])root.right = self.getBSTwithPreTin(pre[order+1:], tin[order+1:])return rootclass treeNode:def __init__(self, x):self.left = Noneself.right = Noneself.val = xif __name__ == '__main__':solution = Solution()preorder_seq = [1, 2, 4, 7, 3, 5, 6, 8]middleorder_seq = [4, 7, 2, 1, 5, 3, 8, 6]treeRoot1 = solution.getBSTwithPreTin(preorder_seq, middleorder_seq)preorder_seq = [1, 2, 3]middleorder_seq = [2, 1, 3]treeRoot2 = solution.getBSTwithPreTin(preorder_seq, middleorder_seq)print(solution.HasSubtree(treeRoot1, treeRoot2))这篇关于剑指offer：输入两棵二叉树A，B，判断B是不是A的子结构（Python）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
