# 根据前、中、后序数组构造二叉树
根据两个遍历数组生成二叉树，主要是固定住一个根节点，然后去另一个数组查找下标，划分数组做左右子树，再递归执行左子树和右子树。
**这里主要讨论的是使用切片的过程中如何确定切片的起始点，即切片的区间，利用的是左子树的长度。**
### 前序和中序构造二叉树
[105\. 从前序与中序遍历序列构造二叉树](https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)
递归加切片， python 中可以使用 index 函数直接获取值的下标。 注意：切片是左闭右开区间，最后一个值取不到
切片的下标如何思考：**利用左子树的长度来辅助思考**。idx 是中序数组中的当前节点下标，所以左子树长度是 idx，所以中序数组分成左右两个数组 `[1,idx]`, `[idx+1,-1]`，其中 `[1,idx]` 的长度是 idx-1+1= idx。因为切片是左闭右开的，因此分成 `[1,idx+1)` 和 `[idx+1,-1]` 两个区间。中序数组就简单了，以 idx 为界分成左右两个区间 `[0,idx)`, `[idx+1,-1]`，因为 idx 已经被用了，因此两个区间都不包含 idx 下标。
```python
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
def dfs(preorder: List[int], inorder: List[int]):
if len(preorder) == 0 or len(inorder) == 0:
return None
root = TreeNode(preorder[0])
idx = inorder.index(preorder[0])
root.left = dfs(preorder[1:idx+1], inorder[:idx])
root.right = dfs(preorder[idx+1:], inorder[idx+1:])
return root
return dfs(preorder, inorder)
```
### 中序和后序构造二叉树
[106\. 从中序与后序遍历序列构造二叉树](https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/)
> 在没有切片的语言中需要重新定义一个函数，然后定义前序、中序、后序的的起始点和终止点，然后迭代！Go 语言有切片，直接传递切片即可！
如何思考切片下标？ **还是利用左子树长度来辅助思考**。idx 是中序遍历当前节点下标，左子树长度就是 idx。中序数组比较简单，idx 节点已经使用了，中序数组以 idx 为界分成左右两个区间 `[0,idx)`，`[idx+1,-1]`。后序数组中左子树长度 idx，因此分成两个数组 `[0,idx)` 和 `[idx,-1)` ，其中 `[0,idx)` 的长度也是 idx。
```python
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
def dfs(inorder: List[int], postorder: List[int]):
if not (len(inorder) > 0 and len(postorder) > 0):
return None
root = TreeNode(postorder[-1])
idx = inorder.index(postorder[-1])
root.left = dfs(inorder[:idx], postorder[:idx])
root.right = dfs(inorder[idx+1:], postorder[idx:-1])
return root
return dfs(inorder, postorder)
```
### 前序和中序构造二叉树
[889\. 根据前序和后序遍历构造二叉树](https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-postorder-traversal/)
* 前序和后序无法唯一确定一棵二叉树，因此写出一种即可
* **将前序数组的第二个值作为左子树的根节点**，在后序数组中找到这个根节点，这个节点的左侧包括这个节点即左子树，右侧即右子树！
* 左右子树无法确定的原因在于：`if preorder[1] == postorder[i]` 将先序数组的第二个元素作为左子树，但第二个元素有可能是右子树的根节点，左子树根节点为空！
如何确定切片的下标呢？**还是借助左子树长度来辅助思考**。前序数组的第一个值和后序数组的最后一个值是相同的，做当前节点值。假设前序数组的第二个值是左子树根节点，则在后序数组中找到这个值的下标，因为这个值属于左子树，因此**左子树的长度是**`[0:idx]` 数组的长度 idx+1。所以前序数组可以分成 `[1,idx+2)` 和 `[idx+2,-1]` 两个数组，其中 `[1,idx+2)` 的长度是 idx+1。后序数组就可以分成 `[0,idx+1)`, `[idx+1,-1]` 两个数组，其中 `[0,idx+1)` 的长度是 idx+1
```python
class Solution:
def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
def dfs(preorder: List[int], postorder: List[int]):
if len(preorder)==0:
return None
if len(preorder) == 1:
return TreeNode(preorder[0])
root = TreeNode(preorder[0])
left_val = preorder[1]
idx = postorder.index(left_val)
root.left = dfs(preorder[1:idx+2], postorder[:idx+1])
root.right = dfs(preorder[idx+2:], postorder[idx+1:-1])
return root
return dfs(preorder, postorder)
```