根据一棵树的前序遍历与中序遍历构造二叉树。
Given preorder and inorder traversal of a tree, construct the binary tree.
注意: 你可以假设树中没有重复的元素。
Note: You may assume that duplicates do not exist in the tree.
例如,给出
前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:
3 / \ 9 20 / \ 15 7
由两种遍历结果还原二叉树,是一种很经典的面试题型。其中中序遍历结果必须为已知才能还原二叉树。
本题为前序中序还原二叉树,回顾一下遍历顺序:
看中序遍历,找到根结点,一定可以分成左右子树。例如二叉树:
3 / \ 9 20 / \ 15 7
前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]
前序遍历第一个结点 3 ,就是根结点,找到中序遍历中结点值为 3 的位置:
中序遍历 inorder = [9,3,15,20,7] ^ 以 3 为根结点划分两个左右子树: 3 / \ [9] [15,20,7]
前序遍历第二个结点 9,就是下一个子树的根结点,找到中序遍历中结点值为 9 的位置:
中序遍历 inorder : 3 / \ [9] [15,20,7] ^ 结点 9 为叶子结点,不可再划分: 3 / \ 9 [15,20,7]
前序遍历第三个结点 20,就是下一个子树的根结点,找到中序遍历中结点值为 20 的位置:
中序遍历 inorder : 3 / \ 9 [15,20,7] ^ 以 20 为根结点划分两个左右子树: 3 / \ 9 20 / \ [15] [7]
前序遍历第三个结点 15,就是下一个子树的根结点,找到中序遍历中结点值为 15 的位置:
……
由此可知中序遍历必须为已知条件才可找出出每个子树的根结点。
Java:
class Solution { int[] preorder; int[] inorder; int index_pre = 0; HashMap<Integer, Integer> index_Map = new HashMap<>(); public TreeNode buildTree(int[] preorder, int[] inorder) { this.preorder = preorder; this.inorder = inorder; // 将中序遍历结果的结点值与索引位置映射 for (int i = 0; i < inorder.length; i++) index_Map.put(inorder[i], i); return helper(0, inorder.length - 1); } private TreeNode helper(int left, int right) { // 基线条件 if (left > right) return null; // 按顺序逐个取前序遍历结果,并构造为根结点 int root_val = preorder[index_pre++]; TreeNode root = new TreeNode(root_val); // 查找该根结点在中序遍历中的索引位置 int index_in = index_Map.get(root_val); // 构造递归 root.left = helper(left, index_in - 1); root.right = helper(index_in + 1, right); return root; } }
Python:
Python 中也可以将 index_pre
提升到全局变量,这里为了结构上的整齐,使用的是 nonlocal
关键字。
class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode: def helper(left=0, right=len(inorder)-1): nonlocal index_pre # 基线条件 if left > right: return None # 按顺序逐个取前序遍历结果,并构造为根结点 root_val = preorder[index_pre] root = TreeNode(root_val) # 查找该根结点在中序遍历中的索引位置 index_in = index_map[root_val] # 构造递归 index_pre += 1 root.left = helper(left, index_in-1) root.right = helper(index_in+1, right) return root index_pre = 0 # 将中序遍历结果的结点值与索引位置映射 index_map = {val: index for index, val in enumerate(inorder)} return helper()
本文分享自微信公众号 - 爱写Bug(iCodeBugs),作者:爱写Bug
原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。
原始发表时间:2020-02-17
本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。
我来说两句