根据先序遍历建立二叉树
时间: 2023-05-30 20:03:24 浏览: 62
先序遍历建立二叉树的思路如下:
1. 先读取先序遍历的第一个节点作为根节点。
2. 读取下一个节点,如果该节点小于根节点,则将该节点插入根节点的左子树中,否则插入右子树中。
3. 重复步骤2,直到先序遍历的所有节点都被插入二叉树中。
举个例子:
先序遍历序列为:5 3 2 4 7 6 8。
首先读取5作为根节点,接着读取3,因为3小于5,所以插入5的左子树中,形成如下结构:
```
5
/
3
```
接着读取2,因为2小于3,所以插入3的左子树中,形成如下结构:
```
5
/
3
/
2
```
再读取4,因为4大于3,所以插入3的右子树中,形成如下结构:
```
5
/
3
/ \
2 4
```
接着读取7,因为7大于5,所以插入5的右子树中,形成如下结构:
```
5
/ \
3 7
/ \ \
2 4 6
\
8
```
最后读取6和8,分别插入7的右子树和8的右子树中,建立完整的二叉树。
代码实现如下(使用链表存储二叉树):
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def buildTree(self, preorder: List[int]) -> TreeNode:
if not preorder:
return None
root = TreeNode(preorder[0])
i = 1
while i < len(preorder) and preorder[i] < root.val:
i += 1
root.left = self.buildTree(preorder[1:i])
root.right = self.buildTree(preorder[i:])
return root
```
时间复杂度为O(nlogn),空间复杂度为O(logn),其中n为二叉树节点数。