给定一个二叉树的中序与后序遍历结果,请你根据两个序列构造符合这两个序列的二叉树。
数据范围:二叉树的节点数满足 ,节点上的值满足 ,保证节点的值各不相同
例如输入[2,1,4,3,5],[2,4,5,3,1]时,
根据中序遍历的结果[2,1,4,3,5]和后序遍历的结果[2,4,5,3,1]可构造出二叉树{1,2,3,#,#,4,5},如下图所示:
[1],[1]
{1}
[2,1,4,3,5],[2,4,5,3,1]
{1,2,3,#,#,4,5}
int[] post; HashMap<Integer,Integer> inorderMap = new HashMap<Integer,Integer>(); public TreeNode buildTree (int[] inorder, int[] postorder) { for(int i = 0;i<inorder.length;i++){ inorderMap.put(inorder[i],i); } // write code here post = postorder; int len = inorder.length; return build(0,len - 1,0,len -1); } private TreeNode build(int inleft,int inright,int postleft,int postright){ if(inleft > inright || postleft > postright){ return null; } int value = post[postright]; int index = inorderMap.get(value); TreeNode root = new TreeNode(value); root.left = build(inleft,index - 1,postleft,postleft+index-inleft -1); root.right = build(index+1,inright,postleft+index-inleft,postright -1); return root; }
思路:
1.中序遍历顺序:左根右;后序遍历顺序:左右根;根据给出的后序遍历数组可知,数组末元素为根结点值;取出该结点,作为根结点的值。
2.根据中序遍历顺序,找出根结点位置rootIdx;在中序遍历数组中,该结点左边元素为左子树结点值,右边为右子树结点值;在后序遍历数组中,可知从0到rootIdx为左子树结点,从rootIdx到倒数第二个元素为右子数结点。
3.根据中序遍历左子数,后序遍历左子数数组初始化左子树,作为根结点的左子树;根据中序遍历右子数,后序遍历右子数数组初始化右子树,作为根结点的右子树;
4.返回根结点
public class Solution { public TreeNode buildTree (int[] inorder, int[] postorder) { for (int i = 0; i < inorder.length; i++) map.put(inorder[i], i); return help(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1); } public Map<Integer, Integer> map = new HashMap<>(); public TreeNode help(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) { if (inStart > inEnd) return null; int idx = map.get(postorder[postEnd]); int l = idx - inStart; TreeNode root = new TreeNode(postorder[postEnd]); root.left = help(inorder, inStart, idx-1, postorder, postStart, postStart+l-1); root.right = help(inorder, idx+1, inEnd, postorder, postStart+l, postEnd-1); return root; } }
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param inorder int整型一维数组 中序遍历序列 * @param postorder int整型一维数组 后序遍历序列 * @return TreeNode类 */ public TreeNode buildTree (int[] inorder, int[] postorder) { // write code here if(inorder.length != postorder.length || inorder == null || inorder.length == 0) return null; int rootVal = postorder[postorder.length - 1]; // 后序遍历的最后一个元素是根节点 TreeNode tree = new TreeNode(rootVal); // 构建根节点 // 找到根节点在中序遍历中的位置 int rootIndex = 0; for(int i = 0; i < inorder.length; i++){ if(inorder[i] == rootVal){ rootIndex = i; break; } } // 将序列划分为左右两个子树部分,分别进行重构 tree.left = buildTree(Arrays.copyOfRange(inorder, 0, rootIndex), Arrays.copyOfRange(postorder, 0, rootIndex)); tree.right = buildTree(Arrays.copyOfRange(inorder, rootIndex + 1, inorder.length), Arrays.copyOfRange(postorder, rootIndex, postorder.length - 1)); return tree; } }