题目
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗二叉树。
例：
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]
方法：递归
- 判断二叉树是否为空
- 后序遍历为左右中，所以我们可以通过后序遍历的列表得到根节点（或子树的中间节点）的值 root_val
- 中序遍历为左中右，即根节点将左子树和右子树的节点值分开，所以我们可以通过后序遍历得到的根节点（或子树的中间节点）值来分割中序遍历的列表，使其分为左子树节点 inorder_left 和右子树节 inorder_right 点两个部分
- 即使使用不同的遍历方法，该二叉树左右子树的节点个数是固定的，那么在分割后序遍历的列表时，可以通过 inorder_left（或 inorder_right）的长度来进行分割
- 通过不断的调用函数最后得到二叉树
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def buildTree(self, inorder, postorder):
if not inorder:
return None
root_val = postorder[-1]
root = TreeNode(root_val)
separator = inorder.index(root_val)
inorder_left = inorder[ : separator]
inorder_right = inorder[separator + 1: ]
postorder_left = postorder[ : len(inorder_left)]
postorder_right = postorder[len(inorder_left): len(postorder) - 1]
root.left = self.buildTree(inorder_left, postorder_left)
root.right = self.buildTree(inorder_right, postorder_right)
return root
相关知识
-
index(element)：
list.index()
返回指定值首次出现的位置
element： 要搜索的值
报错
-
if not x 和 if x == None：
IndexError: list index out of range
因为 inorder 是列表，所以此处的inorder == None应该为not inorder
例：
若x = []，那么x == None的结果是False，而not x的结果是True
若y = None，那么y == None的结果是True，not y的结果也是True
参考
代码相关：https://programmercarl.com/0106.%E4%BB%8E%E4%B8%AD%E5%BA%8F%E4%B8%8E%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97%E6%9E%84%E9%80%A0%E4%BA%8C%E5%8F%89%E6%A0%91.html
index：https://www.w3school.com.cn/python/ref_list_index.asp
报错：https://www.freesion.com/article/2082559344/
