重建二叉树
重建二叉树
http://www.nowcoder.com/questionTerminal/8a19cbe657394eeaac2f6ea9b0f6fcf6
递归建立二叉树。
public class Solution {
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
private TreeNode create(int[] pre, int[] in, int _i, int _j, int i, int j){
if (i > j || i < 0) return null;
if (j-i == 0) {
return new TreeNode(pre[_i]);
}
int k = 0;
while (in[k] != pre[_i]) ++k;
TreeNode treeNode = new TreeNode(pre[_i]);
treeNode.left = create(pre, in, _i+1, _i+(k-i), i, k-1);
treeNode.right = create(pre, in, _i+(k-i)+1, _j, k+1, j);
return treeNode;
}
public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
return create(pre, in,0, pre.length-1, 0, in.length-1);
}
}
投递中科院自动化所等公司10个岗位 >
