重建二叉树
重建二叉树
https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=13&tqId=23282&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D13
import java.util.*;
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
int[] preorder;
HashMap<Integer, Integer> dic = new HashMap<>();
public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
this.preorder = pre;
for(int i = 0; i < pre.length;i++)
dic.put(vin[i], i);
return recur(0, 0, vin.length -1);
}
TreeNode recur(int root, int left, int right){
if(left > right) return null;
TreeNode node = new TreeNode(preorder[root]);
int i = dic.get(preorder[root]);
node.left = recur(root + 1, left, i - 1);
node.right = recur(root + 1 - left +i, i+1 ,right);
return node;
}
}