二叉树的序列构造方法
二叉树是计算机科学中重要的数据结构之一，它具有良好的层次性、可递归处理、能够高效地支持查找、插入和删除操作等优点。而构造一颗二叉树的方式则多种多样。本文将就二叉树的序列构造方法从多个角度进行分析。
1. 按照树的层次遍历构造
二叉树的层次遍历是按照树的层次由上至下、由左至右进行的。根据这种方式可以构造一颗二叉树。具体实现方法是如下：
- 先将根节点压入队列中作为起始点。
- 从队列中依次取出一个节点，并从输入的序列中取出下一个元素进行判断。如果该元素不为null，则将其赋值给节点，同时将该节点的左右儿子节点分别压入队列中作为下一步的起始点。如果该元素为null，则将该节点的左右儿子节点都赋值为null。
- 重复步骤2，直到输入序列全部被处理完毕。
该方法的时间复杂度为O(N)，其中N为二叉树的节点数。代码实现如下：
```python
def buildTreeFromLevelOrderTraversal(lst):
if not lst:
return None
queue = []
root = TreeNode(lst[0])
queue.append(root)
i = 1
while i < len(lst):
currNode = queue.pop(0)
if lst[i] is not None:
currNode.left = TreeNode(lst[i])
queue.append(currNode.left)
if i+1 < len(lst) and lst[i+1] is not None:
currNode.right = TreeNode(lst[i+1])
queue.append(currNode.right)
i += 2
return root
```
2. 按照前序遍历构造
前序遍历即先访问根节点，再访问左子树，最后访问右子树。可以按照这种顺序来构造一颗二叉树，具体实现方法如下：
- 从输入序列中取出下一个元素作为当前节点的值。
- 如果该元素为null，则返回None。
- 如果该元素不为null，则先创建一个节点对象，将该元素赋值给该节点，并向下递归构造该节点的左子树和右子树。
该方法的时间复杂度为O(N)，其中N为二叉树的节点数。代码实现如下：
```python
def buildTreeFromPreorderTraversal(lst):
if not lst:
return None
val = lst.pop(0)
if val is None:
return None
node = TreeNode(val)
node.left = buildTreeFromPreorderTraversal(lst)
node.right = buildTreeFromPreorderTraversal(lst)
return node
```
3. 按照中序遍历构造
中序遍历即先访问左子树，再访问根节点，最后访问右子树。可以按照这种顺序来构造一颗二叉树，具体实现方法如下：
- 先处理左子树，递归构造左子树并返回其根节点节点对象。
- 从输入序列中取出下一个元素作为当前节点的值，并创建节点对象。
- 处理右子树，递归构造右子树并返回其根节点对象。
- 将创建的节点对象的左孩子指向左子树的根节点，右孩子指向右子树的根节点。
- 返回创建的节点对象。
该方法的时间复杂度为O(NlogN)，其中N为二叉树的节点数，logN为二叉树的高度。代码实现如下：
```python
def buildTreeFromInorderTraversal(inorder, start, end):
if start > end:
return None
mid = (start + end) // 2
node = TreeNode(inorder[mid])
node.left = buildTreeFromInorderTraversal(inorder, start, mid-1)
node.right = buildTreeFromInorderTraversal(inorder, mid+1, end)
return node
```
4. 按照中序和后序遍历构造
中序遍历和后序遍历都可以确定一颗二叉树，具体实现方法如下：
- 首先得到后序遍历序列的最后一个元素作为根节点的值，并创建根节点对象。
- 在中序序列中查找根节点的值，将原序列分为左子树和右子树，并记录左子树和右子树的长度。
- 递归构造左子树和右子树，并返回根节点对象。
该方法的时间复杂度为O(NlogN)，其中N为二叉树的节点数，logN为二叉树的高度。代码实现如下：
```python
def buildTreeFromInorderAndPostorderTraversal(inorder, postorder):
if not inorder or not postorder:
return None
root = TreeNode(postorder[-1])
rootIndex = inorder.index(root.val)
root.left = buildTreeFromInorderAndPostorderTraversal(inorder[:rootIndex], postorder[:rootIndex])
root.right = buildTreeFromInorderAndPostorderTraversal(inorder[rootIndex+1:], postorder[rootIndex:-1])
return root
```
综上所述，二叉树的构造方式多种多样，包括按照层次遍历、前序遍历、中序遍历、中序和后序遍历等方式。每种方法都有其适用的场景和复杂度，具体应根据实际问题选择合适的构造方法。
