刷題的日常Day1--重建二叉樹

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

題目分析：重建二叉樹幾乎是每個學習數據結構學生應該掌握的基本功，但是根據課程要求的不同，有的只要求會手動畫圖就行，不要求代碼實現，今天我們就來用代碼實現一下二叉樹的重建。

二叉樹重建的過程，1>將先序遍歷的第一個值當做根節點。2>查找中序遍歷中這個值的位置，將中序遍歷中位於該值左側的數據，劃分到根節點的左側，位於該值右邊的數據，劃分到根節點的右側。3>以此類推，直到中序遍歷中的數字全部填充到重建的二叉樹中。

代碼實現：

/** * 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) { return reTreeNode(pre,in,0,pre.length-1,0,in.length); } TreeNode reTreeNode(int [] pre,int [] in ,int firstpre,int endpre,int firstin,int endin){ if (firstpre>endpre||firstin>endin) { return null; } TreeNode treeNode = new TreeNode(pre[firstpre]); for(int i = firstin;i<=endin;i++){ if(in[i]==pre[firstpre]){ treeNode.left = reTreeNode(pre, in, firstpre+1, firstpre+i-firstin, firstin, i-1); treeNode.right=reTreeNode(pre, in, firstpre+i-firstin+1, endpre, i+1, endin); break; } } return treeNode; }}

推薦閱讀：