二叉树攻略之：从中序与后序遍历序列构造二叉树

二叉树攻略之：从中序与后序遍历序列构造二叉树

题目

根据一棵树的中序遍历与后序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

例如，给出

中序遍历 inorder = [9,3,15,20,7]后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树：

3 / \ 9 20 / \ 15 7

解题思路

根据题意, 我们知道后序遍历的形式是先遍历左子树点，然后是右子树，最后是根节点；中序遍历的形式是，先左子树，再根节点，最后是右节点；

只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。我们可以发现后序遍历的数组最后一个元素代表的即为根节点，由于同一颗子树的后序遍历和中序遍历的长度显然是相同的，因此我们就可以对应到后序遍历的结果中，对上述形式中的所有左右括号进行定位。

这样以来，我们就知道了左子树的后序遍历和中序遍历结果，以及右子树的后序遍历和中序遍历结果，我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。

在中序遍历中对根节点进行定位时，我们可以考虑使用哈希表来帮助我们快速地定位根节点。对于哈希映射中的每个键值对，键表示一个元素（节点的值），值表示其在中序遍历中的出现位置，代码实现如下：

代码实现

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { // 定义哈希表用于定位中序数组根节点的的位置 public HashMap map = new HashMap(); int[] post; public TreeNode buildTree(int[] inorder, int[] postorder) { for (int i = 0; i < inorder.length; i++){ map.put(inorder[i], i); } post = postorder; TreeNode root = helper(0, inorder.length - 1, 0, post.length - 1); return root; } public TreeNode helper(int inStart, int inEnd, int postStart, int{ if (inStart > inEnd || postStart > postEnd) return null; int val = post[postEnd]; int rootPos = map.get(val); TreeNode node = new TreeNode(val); node.left = helper(inStart, rootPos -1 , postStart, postStart + rootPos - inStart -1); node.right = helper(rootPos+1, inEnd, postStart + rootPos - inStart, postEnd - 1); return

最后

复杂度分析：

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。