一, 关于 Java 中的 Arrays.copyOfRange()方法
要使用这个方法, 首先要 import java.util.*;
Arrays.copyOfRange(T[ ] original,int from,int to)
将一个原始的数组 original, 从小标 from 开始复制, 复制到小标 to, 生成一个新的数组.
注意这里包括下标 from, 不包括上标 to.
题目来自牛客网:
输入某二叉树的前序遍历和中序遍历的结果, 请重建出该二叉树. 假设输入的前序遍历和中序遍历的结果中都不含重复的数字. 例如输入前序遍历序列 {1,2,4,7,3,5,6,8} 和中序遍历序列{4,7,2,1,5,3,8,6}, 则重建二叉树并返回.
- import java.util.*;
- /**
- * Definition for binary tree
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
- public class Solution {
- public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
- if(pre.length == 0){
- return null;
- }
- TreeNode node = new TreeNode(pre[0]);
- for(int i = 0;i < in.length; i++){
- if(pre[0] == in[i]){
- node.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
- node.right = reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length));
- }
- }
- return node;
- }
- }
以上是通过递归的方法解决该问题, 每一轮的查找, 主要是通过前序遍历的 root(pre[0]), 来中序遍历中寻找到根节点(in[i]), 则中序遍历中左侧为左子树, 0~i. 相对应本次查找的, 前序遍历中左子树 1~i+1.[根据 Arrays.copyOfRange, 不包括后续值] 同理, 对于每一轮的递归, 它的右子树前序遍历显然是 i+1~pre.length, 中序遍历为 i+1~in.length. 这是一种通过 Java 中自带函数解决问题的方法, 代码简洁易懂.
重建二叉树
来源: http://www.bubuko.com/infodetail-2985746.html