利用先序遍历建立二叉树
时间: 2024-01-08 13:46:25 浏览: 30
先序遍历建立二叉树的过程如下:
1. 读入根节点的值。
2. 如果根节点的值不为空,则创建一个节点,并将读入的值赋给该节点。
3. 继续读入下一个节点的值,如果该节点的值为空,则将该节点设置为 NULL。
4. 递归建立该节点的左子树,即重复步骤 1~3。
5. 递归建立该节点的右子树,即重复步骤 1~3。
具体实现可以参考下面的 Python 代码:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def buildTree(preorder):
def build():
nonlocal i
if i >= len(preorder) or preorder[i] is None:
i += 1
return None
root = TreeNode(preorder[i])
i += 1
root.left = build()
root.right = build()
return root
i = 0
return build()
```
其中,`preorder` 是先序遍历的结果,`build` 函数递归建立二叉树,`i` 表示当前处理到的节点在 `preorder` 中的下标。