题解 | #重建二叉树#
重建二叉树
https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6
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 preOrder int整型一维数组 * @param vinOrder int整型一维数组 * @return TreeNode类 */ public TreeNode reConstructBinaryTree (int[] preOrder, int[] vinOrder) { // write code here if(preOrder.length==0){ return null; } return getResult(preOrder,vinOrder); } private TreeNode getResult(int[] preOrder, int[] vinOrder) { // TODO if(preOrder.length==0){ return null; } TreeNode root = new TreeNode(preOrder[0]); int middle = root.val; int length_left = 0; int length_right = 0; boolean mid = false; for(int i = 0; i < vinOrder.length; length_left++, i++){ if(vinOrder[i] == root.val){ mid = true; break; } } length_right = vinOrder.length-1-length_left; int preleft[] = new int[length_left]; int vinleft[] = new int[length_left]; int preright[] = new int[length_right]; int vinright[] = new int[length_right]; for(int i = 0; i < length_left; i++){ preleft[i] = preOrder[i+1]; vinleft[i] = vinOrder[i]; } for(int i = 0; i < length_right; i++){ preright[i] = preOrder[length_left+i+1]; vinright[i] = vinOrder[length_left+i+1]; } root.left = getResult(preleft,vinleft); root.right = getResult(preright,vinright); return root; } }