【问题描述】设二叉树按二叉链表存放,写算法判别一棵二叉树是否是一棵正则二叉树。正则二叉树是指在二叉树中不存在子树个数为1的结点。 【输入说明】二叉树的前序和中序遍历序列,以此构造二叉树的链式存储 【输出说明】若该二叉树是一棵正则二叉树,则输出Yes,否则输出No 【样例输入】 ABHDCEFG HBDAEFCG 【样例输出】 No
时间: 2023-12-01 17:02:29 浏览: 23
以下是该问题的一种解法:
1. 根据前序遍历和中序遍历构建二叉树
2. 从根节点开始遍历每个节点,若该节点有且仅有一个子节点,则该二叉树不是正则二叉树,返回 No
3. 若遍历完所有节点都满足要求,则该二叉树是正则二叉树,返回 Yes
以下是该解法的Python代码实现:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def buildTree(preorder, inorder):
if not preorder or not inorder:
return None
root = TreeNode(preorder[0])
idx = inorder.index(preorder[0])
root.left = buildTree(preorder[1:idx+1], inorder[:idx])
root.right = buildTree(preorder[idx+1:], inorder[idx+1:])
return root
def isRegularTree(root):
if not root:
return True
if not root.left and not root.right:
return True
if root.left and not root.right:
return isRegularTree(root.left)
if not root.left and root.right:
return isRegularTree(root.right)
return False
preorder = input().strip()
inorder = input().strip()
root = buildTree(preorder, inorder)
if isRegularTree(root):
print("Yes")
else:
print("No")
```
该算法的时间复杂度为 $O(n^2)$,空间复杂度为 $O(n)$。其中 $n$ 是二叉树的节点数。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)