题解 | #重建二叉树#
重建二叉树
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 //前序遍历 1,2,4,7,3,5,6,8 //4,7,2,1,5,3,8,6第一个节点为根节点 if(preOrder.length==0||vinOrder.length==0){ return null; } int root=preOrder[0];//根节点 TreeNode r=new TreeNode(root); //去中序遍历里面找到该值 int rIndex=0; for(int i=0;i<vinOrder.length;i++){ if(vinOrder[i]==root){ rIndex=i; } } //左边元素个数为rIndex,右边元素为len-rIndex int[] preLeft=Arrays.copyOfRange(preOrder,1,rIndex+1); int[] preRight=Arrays.copyOfRange(preOrder,rIndex+1,preOrder.length); int[] inLeft=Arrays.copyOfRange(vinOrder,0,rIndex); int[] inRight=Arrays.copyOfRange(vinOrder,rIndex+1,vinOrder.length); r.left=reConstructBinaryTree(preLeft,inLeft); r.right=reConstructBinaryTree(preRight,inRight); return r; } }