題目描述

輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并返回。

解題思路

先找出根節點，然后利用遞歸方法構造二叉樹

代碼實現

import java.util.*;/*** Definition for binary tree* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/public class Solution {public TreeNode reConstructBinaryTree(int [] pre,int [] in) {if (null == pre || null == in) {return null;}if (0 == pre.length || 0 == in.length) {return null;}if (pre.length != in.length) {return null;}TreeNode root = new TreeNode(pre[0]);for (int i = 0; i < pre.length; i++) {if (pre[0] == in[i]) {root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1),Arrays.copyOfRange(in, 0, i));root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length),Arrays.copyOfRange(in, i+1, in.length));}}return root;} }

部分代碼解析

Arrays.copyOfRange(pre,1,i+1)

要使用這個方法，首先要import java.util.*;

Arrays.copyOfRange(T[ ] original,int from,int to)

將一個原始的數組original，從下標from開始復制，復制到上標to，生成一個新的數組。

注意這里包括下標from，不包括上標to。

因此，若要拷貝pre數組中 1~i 的元素，則需要將 to 參數設置為 i+1；

同理，

Arrays.copyOfRange(in,0,i)

是用來構造中序遍歷數組 in 的 0~(i-1) 的元素。

總結

以上是生活随笔為你收集整理的剑指Offer（Java实现）重建二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。