引言
树是由 n（n≥0）个结点组成的有限集合。
当 n = 0 时，称为空树；
当 n > 0 时，有一个特殊的节点称为根结点（root），它没有前驱结点；其它结点分为 m 棵互不相交的子树。
树
我下面举出的三个例子，均是以1,2,3,4,5的方式排序的。可以通过这个排序来区分三种遍历情况。
前序遍历
前序遍历：根结点 --> 左子树 --> 右子树
中序遍历
前序遍历： 左子树 -->根结点 --> 右子树
后序遍历
前序遍历： 左子树 --> 右子树 -->根结点
根据前中序列求出树
class Solution:def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:def recur(root, left, right):if left > right: returnnode = TreeNode(preorder[root])i = dic[preorder[root]]node.left = recur(root + 1, left, i - 1)node.right = recur(i - left + root + 1, i + 1, right)return nodedic, preorder = {}, preorderfor i in range(len(inorder)):dic[inorder[i]] = ireturn recur(0, 0, len(inorder) - 1)- 这个前中序列，因为在分析的过程中是需要两种序列一起分析的，所以在代码中实现就是先利用前序的特点，根左右，然后将中序遍历得到树。
- 代码的主要核心是，左子树和右子树，因为根节点会与两个子树有关系，即理解了左右子树，根可以很快理解。首先要明确的一点是不管是何种遍历方法，左子树的左边界，始终是left，右边界始终是i - 1，因为i为遍历中序遍历的一个元素，在中序遍历中，顺序为左根右，所以左子树的右边界是i - 1，而左子树的根节点是root + 1，因为在前序遍历中，顺序是根左右，左在根的后面，所以是root + 1，然后右子树，右边界始终是right，左边界是i + 1（在中序遍历中是根左右，右是在根的右边，所以是i + 1），然后后面一个重要的点是前序遍历返回值是0(因为前序遍历的起始索引是0)，中序遍历的返回值是（0，len(inorder） - 1)（中序遍历的范围是0，len(inorder） - 1)）。还有一个核心的知识是右子树的根节点减去左子树的根节点，答案是i - left，因为还是在前序遍历中，左根右，i - left是右子树根节点和左子树根节点的差值。
根据中后序列求出树
class Solution:def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:def recur(left, right, post_root):if left > right: return Nonenode = TreeNode(postorder[post_root]) i = dic[postorder[post_root]] node.left = recur(left, i - 1, post_root - (right - i) - 1) node.right = recur(i + 1, right, post_root - 1) return nodedic = {} for i in range(len(inorder)):dic[inorder[i]] = ireturn recur(0, len(inorder) - 1, len(postorder) - 1)这个中后序列遍历分析跟之前的前中也是一个思想，二者可以一起思考。
- 这个中后序列，因为在分析的过程中是需要两种序列一起分析的，所以在代码中实现就是先利用后序的特点，左右根，然后将中序遍历得到树。
- 代码的主要核心是，左子树和右子树，因为根节点会与两个子树有关系，即理解了左右子树，根可以很快理解。首先要明确的一点是不管是何种遍历方法，然后右子树，右边界始终是right，左边界是i + 1（在中序遍历中是根左右，右是在根的右边，所以是i + 1），右子树的根节点是post_root - i,因为在后序遍历中是左右根，右在根的前面。左子树的左边界，始终是left，右边界始终是i - 1，因为i为遍历中序遍历的一个元素，在中序遍历中，顺序为左根右，所以左子树的右边界是i - 1，而左子树的根节点是post_root - （right - i）1，因为右子树的根节点和左子树的根节点差值是right - i，因为在后序遍历中右在根的后面，然后后面一个重要的点是后序遍历返回值是0，len(postorder） - 1)(中序遍历的范围是0，len(postorder） - 1))，中序遍历的返回值是（0，len(inorder） - 1)（中序遍历的范围是0，len(inorder） - 1)）。
