题目: 根据一棵树的前序遍历与中序遍历构造二叉树。
来源: https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
总结: 法一的解法只适用于前序中序,后序中序.不适用于前序后序,法二解法对这三种都适用,缺点是内存消耗大.
法一: 官方代码
思路: 利用分治和递归,对前序遍历元素进行遍历,再对中序遍历进行递归回溯,关键是要观察出两个遍历的结构特点,以及递归的写法.
# Definition for a binary tree node. class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None from typing import List class Solution: def buildTree(self, preorder, inorder): # global pre_idx def helper(in_left=0, in_right=len(inorder)): nonlocal pre_idx # global pre_idx # 如果左 if in_left == in_right: return None # 先找出前序遍历索引对应的数 root_val = preorder[pre_idx] # 再将其建一个节点 root = TreeNode(root_val) # 求出中序遍历中该元素对应的索引 index = idx_map[root_val] # 索引加一 pre_idx += 1 # 寻找节点的左节点,(in_left, index)是左子树所有的节点值 root.left = helper(in_left, index) # 寻找节点的右节点 root.right = helper(index + 1, in_right) return root # 对中序遍历建立一个字典,key是inorder中的值,value是值对应的索引 idx_map = {val: idx for idx, val in enumerate(inorder)} pre_idx = 0 return helper() if __name__ == '__main__': def list_to_binarytree(a): if a[0] is None: return [] stack = [] root = TreeNode(a.pop(0)) stack.append(root) while a: # 一层一层的遍历 stack_next = stack stack = [] # a有可能提前变为[],这时直接结束内循环 while stack_next and a: # 注意这里的b不能是空对象的地址,否则会出错 b = stack_next.pop(0) # 为了保证结构的统一特别引入了555,stack中555表示这里是一个空节点, # stack中只有两种值一种是555,另一种是节点的地址 # 上一层的空节点对应下一层a中的两个None,依次弹出 if b == 555: a.pop(0) a.pop(0) continue # 如果某个节点为None,则将其地址标记为555 if a[0] == None: a.pop(0) stack.append(555) else: b.left = TreeNode(a.pop(0)) stack.append(b.left) if a[0] == None: a.pop(0) stack.append(555) else: b.right = TreeNode(a.pop(0)) stack.append(b.right) duixiang = Solution() a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, None, None, None, 11, 12, None, None, None, None, None, None, None, None, None, None, None, None, 13, 14] preorder = [1, 2, 4, 8, 9, 5, 10, 3, 6, 7, 11, 13, 14, 12] inorder = [8, 4, 9, 2, 10, 5, 1, 6, 3, 13, 11, 14, 7, 12] root = list_to_binarytree(a) a = duixiang.buildTree(preorder, inorder)
法二: 模仿889的写法,每次取前序遍历的第一个元素,缺点是内存消耗大
# Definition for a binary tree node. class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None # 执行用时 :196 ms, 在所有 python3 提交中击败了70.59% 的用户 # 内存消耗 :87.3 MB, 在所有 python3 提交中击败了72.23%的用户 # 模仿889由前序和后序构造二叉树的写法 class Solution: def buildTree(self, preorder, inorder): def recursion(preorder=preorder, inorder= inorder): if len(inorder) == 0: return None root = TreeNode(preorder[0]) if len(preorder) == 1 : return root L = inorder.index(root.val) root.left = recursion(preorder[1:L+1], inorder[:L]) root.right = recursion(preorder[L+1:], inorder[L+1:]) return root return recursion() if __name__ == '__main__': def list_to_binarytree(a): if a[0] is None: return [] stack = [] root = TreeNode(a.pop(0)) stack.append(root) while a: # 一层一层的遍历 stack_next = stack stack = [] # a有可能提前变为[],这时直接结束内循环 while stack_next and a: # 注意这里的b不能是空对象的地址,否则会出错 b = stack_next.pop(0) # 为了保证结构的统一特别引入了555,stack中555表示这里是一个空节点, # stack中只有两种值一种是555,另一种是节点的地址 # 上一层的空节点对应下一层a中的两个None,依次弹出 if b == 555: a.pop(0) a.pop(0) continue # 如果某个节点为None,则将其地址标记为555 if a[0] == None: a.pop(0) stack.append(555) else: b.left = TreeNode(a.pop(0)) stack.append(b.left) if a[0] == None: a.pop(0) stack.append(555) else: b.right = TreeNode(a.pop(0)) stack.append(b.right) duixiang = Solution() a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, None, None, None, 11, 12, None, None, None, None, None, None, None, None, None, None, None, None, 13, 14] preorder = [1, 2, 4, 8, 9, 5, 10, 3, 6, 7, 11, 13, 14, 12] inorder = [8, 4, 9, 2, 10, 5, 1, 6, 3, 13, 11, 14, 7, 12] root = list_to_binarytree(a) a = duixiang.buildTree(preorder, inorder) print(a)