设二叉树按二叉链表存放,写算法判别一棵二叉树是否是一棵正则二叉树。正则二叉树是指在二叉树中不存在子树个数为1的结点。 【输入说明】二叉树的前序和中序遍历序列,以此构造二叉树的链式存储
时间: 2023-11-14 21:10:30 浏览: 113
编写采用二叉链表形式存储的二叉树的创建、先序、中序、后序和按层遍历的算法
5星 · 资源好评率100%
算法思路:
对于一个节点,如果其左子树或右子树为空,则其子树个数为1,不满足正则二叉树的定义。否则,递归判断其左右子树是否为正则二叉树。
具体实现:
1. 根据前序遍历序列和中序遍历序列构造二叉树。
2. 编写一个函数判断当前节点的子树是否为正则二叉树,若是,则返回子树中节点数量,否则返回-1。
3. 在判断根节点是否为正则二叉树时,若其左右子树都为正则二叉树且子树节点数量都不为1,则该树为正则二叉树。
完整代码如下:
```python
# 定义二叉树节点
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
class Solution:
def buildTree(self, preorder, inorder):
if not preorder or not inorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
idx = inorder.index(root_val)
root.left = self.buildTree(preorder[1:idx+1], inorder[:idx])
root.right = self.buildTree(preorder[idx+1:], inorder[idx+1:])
return root
def isRegularBT(self, root):
if not root:
return 0
left_cnt = self.isRegularBT(root.left)
right_cnt = self.isRegularBT(root.right)
if left_cnt == -1 or right_cnt == -1:
return -1
if left_cnt == 1 and not root.left or right_cnt == 1 and not root.right:
return -1
return left_cnt + right_cnt + 1
def isRegularBinaryTree(self, preorder, inorder):
root = self.buildTree(preorder, inorder)
if self.isRegularBT(root) == -1:
return False
else:
return True
```
例如,对于二叉树的前序遍历序列为[1, 2, 4, 5, 3, 6, 7],中序遍历序列为[4, 2, 5, 1, 6, 3, 7]的二叉树,可以使用以下代码进行判断:
```python
preorder = [1, 2, 4, 5, 3, 6, 7]
inorder = [4, 2, 5, 1, 6, 3, 7]
s = Solution()
print(s.isRegularBinaryTree(preorder, inorder))
```
输出结果为True,说明该二叉树是正则二叉树。
阅读全文