Construct Binary Tree from Preorder and Inorder Traversal
今天是一道有關(guān)二叉樹的題目胎撤，來自LeetCode默穴，難度為Medium挖炬，Acceptance為27.2%支鸡。
題目如下
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
解題思路及代碼見閱讀原文
回復(fù)0000查看更多題目
解題思路
首先镰官，還是看到二叉樹剧蚣，想到二叉樹的三種遍歷方式支竹。
然后，該題中由前序遍歷的結(jié)果和中序遍歷的結(jié)果構(gòu)造二叉樹顯然可以采用前序遍歷的方法遞歸的方法鸠按，構(gòu)造根節(jié)點(diǎn)和它的左右子樹唾戚。
思路如下：
首先，在前序遍歷中待诅，根節(jié)點(diǎn)是第一個(gè)元素叹坦；而在中序遍歷中根節(jié)點(diǎn)在中間，它的左邊是它的左子樹卑雁，右邊是它的右子樹募书。因?yàn)轭}目中已經(jīng)寫明，沒有重復(fù)的節(jié)點(diǎn)测蹲，所以很容易找到根節(jié)點(diǎn)在中序遍歷中的位置莹捡，然后將其分成左右子樹兩個(gè)子數(shù)組。
然后扣甲，根據(jù)中序遍歷中左右子樹的長度篮赢，在前序遍歷中截取相同長度的子數(shù)組，與中序遍歷的兩個(gè)子數(shù)組相對(duì)應(yīng)琉挖。
最后启泣，遞歸調(diào)用這個(gè)方法，就可以得到左右子樹示辈。
代碼如下
Java版
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
*@param preorder : A list of integers that preorder traversal of a tree
*@param inorder : A list of integers that inorder traversal of a tree
*@return : Root of a tree
*/
public TreeNode buildTree(int[] preorder, int[] inorder) {
// write your code here
return buildTree(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
}
private TreeNode buildTree(int[] preorder, int[] inorder, int preStart, int preEnd, int inStart, int inEnd){
if(preStart > preEnd || inStart > inEnd)
return null;
int val = preorder[preStart];
TreeNode root = new TreeNode(val);
int temp = inStart;
while(inorder[temp] != val)
temp++;
root.left = buildTree(preorder, inorder, preStart + 1, preStart + 1 + temp - 1 - inStart, inStart, temp - 1);
root.right = buildTree(preorder, inorder, preEnd - (inEnd - temp - 1), preEnd, temp + 1, inEnd);
return root;
}
}
關(guān)注我
該公眾號(hào)會(huì)每天推送常見面試題寥茫，包括解題思路是代碼，希望對(duì)找工作的同學(xué)有所幫助
image
