扩展先序遍历创建一棵二叉树的算法思想
时间: 2023-08-30 14:05:48 浏览: 84
扩展先序遍历创建一棵二叉树的算法思想如下:
1. 读入当前节点的值。
2. 如果当前节点的值为"#", 则返回空节点。
3. 如果当前节点的值不为"#", 则创建一个新节点,并将其值设置为当前节点的值。
4. 递归创建左子树:调用创建二叉树的函数,返回的树作为当前节点的左子树。
5. 递归创建右子树:调用创建二叉树的函数,返回的树作为当前节点的右子树。
6. 返回当前节点。
算法思想的实现过程如下:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def createTree(preorder):
if not preorder:
return None
val = preorder.pop(0)
if val == "#":
return None
root = TreeNode(val)
root.left = createTree(preorder)
root.right = createTree(preorder)
return root
```
其中,preorder是扩展先序遍历的序列,函数返回创建的二叉树的根节点。