105. 从前序与中序遍历序列构造二叉树

通过前序遍历,前序遍历的第一个节点是头节点,这样我们就找到了头节点,现在去中序遍历中找到头节点的位置,头节点左边的是左子节点树,右边是右子节点树,我们只需要对每一个节点都进行这么处理就行,不断切分数组,找到每一个头节点class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { // 没节点了 if (preorder.length 0) { return null; } // 前序第一个是根 int rootVal preorder[0]; TreeNode root new TreeNode(rootVal); // 在中序中找根的位置 int index 0; while (inorder[index] ! rootVal) { index; } // 切左子树 int[] leftPre Arrays.copyOfRange(preorder, 1, index 1); int[] leftIn Arrays.copyOfRange(inorder, 0, index); // 切右子树 int[] rightPre Arrays.copyOfRange(preorder, index 1, preorder.length); int[] rightIn Arrays.copyOfRange(inorder, index 1, inorder.length); // 递归构造 root.left buildTree(leftPre, leftIn); root.right buildTree(rightPre, rightIn); return root; } }