本文共 2511 字，大约阅读时间需要 8 分钟。
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。class Solution: # 返回构造的TreeNode根节点 def reConstructBinaryTree(self, preorder, inorder): """ 与树有关的题目一般来讲可以先尝试使用递归方法求解。 :param preorder: 一棵树的先序遍历结果 :param inorder: 同一棵树的中序遍历结果 :return: 构造的树的根节点 """ def helper(preorder_start, preorder_end, inorder_start, inorder_end): """ 通过传下标代替传列表，可以减少中间的内存开销。 四个参数分别代表了当前子树的先序遍历和中序遍历的结果，根据这四个参数可以从总体的 先序遍历和中序遍历中找到当前子树的先序遍历和中序遍历。 :return: 当前子树的根节点 """ # 对于一棵子树，其先序遍历的第一个节点就是根节点 root = TreeNode(preorder[preorder_start]) # 如果当前子树只有一个节点(这时这个子树其实是叶子节点)，这是我们的递归出口 if preorder_start == preorder_end: # 这里增加了一个输入合法性判断 if inorder_start == inorder_end \ and preorder[preorder_end] == inorder[inorder_end]: return root else: return None # 然后从中序遍历中找到这个根节点，按照中序遍历的顺序，根节点左边的是左子树的节点， # 右边的是右子树的节点 i = inorder_start while i <= inorder_end: if inorder[i] == root.val: break i += 1 # 输入合法性判断，确保这个根节点在中序遍历中能找到 if inorder[i] != root.val: return None left_length = i - inorder_start # 左子树的节点数 # 左右子树的先序遍历下标 preorder_left_start = preorder_start + 1 preorder_left_end = preorder_left_start + left_length - 1 preorder_right_start = preorder_left_end + 1 preorder_right_end = preorder_end # 左右子树的中序遍历的下标 inorder_left_start = inorder_start inorder_left_end = i - 1 inorder_right_start = i + 1 inorder_right_end = inorder_end # 如果存在左右子树，则递归下去 if left_length > 0: root.left = helper(preorder_left_start, preorder_left_end, inorder_left_start, inorder_left_end) if left_length < preorder_end - preorder_start: root.right = helper(preorder_right_start, preorder_right_end, inorder_right_start, inorder_right_end) return root if not preorder or not inorder: # 验证输入合法性 return None return helper(0, len(preorder) - 1, 0, len(inorder) - 1) # 递归构造二叉树
转载于:https://blog.51cto.com/jayce1111/2379451