牛客网-重建二叉树

牛客网-重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

二叉树一般都是递归创建，不然得写多少代码。 本题是由先序和中序重新创建一颗二叉树，首先分析递归的边界。

代码详解

private Map indexForInOrders = new HashMap<>(); public TreeNode reConstructBinaryTree(int[] pre, int[] in) { for (int i = 0; i < in.length; i++) indexForInOrders.put(in[i], i); return reConstructBinaryTree(pre, 0, pre.length - 1, 0); } //参数的意思，pre代表的是先序序列，preL代表序列的最左边，而preR代表序列的最右边，intL表示的是：由于先序序列中的元素在中序序列的定位，可以将中序序列分割成两个，inL表示的就是两个序列的最左边的下标。 private TreeNode reConstructBinaryTree(int[] pre, int preL, int preR, int inL) { if ( preL >preR)//边界条件 return null; TreeNode root = new TreeNode(pre[preL]); int inIndex = indexForInOrders.get(root.val); int leftTreeSize = inIndex - inL; root.left = reConstructBinaryTree(pre, preL + 1, preL + leftTreeSize, inL); root.right = reConstructBinaryTree(pre, preL + leftTreeSize + 1, preR, inL + leftTreeSize + 1); return root; }

*第一次思考这个题，还是不够清晰

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