解题
前序遍历和中序遍历树构造二叉树
根据前序遍历和中序遍历树构造二叉树.
样例
给出中序遍历：[1,2,3]和前序遍历：[2,1,3]. 返回如下的树:
2
/ \
1 3
注意
你可以假设树中不存在相同数值的节点
解题
和上一题很类似的。
前序遍历：根左右
中序遍历：左根右
/**
* 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
if(preorder.length != inorder.length)
return null;
return buildTree(preorder,0,preorder.length - 1,inorder,0,inorder.length - 1);
}
public int findPosition(int[] inorder,int istart,int iend,int r){
for(int i=istart;i<=iend;i++)
if(inorder[i] == r)
return i;
return -1;
}
public TreeNode buildTree(int[] preorder,int pstart,int pend,int[] inorder,int istart,int iend){
if(pstart > pend){
return null;
}
int r = preorder[pstart];
int position = findPosition(inorder,istart,iend,r);
TreeNode root = new TreeNode(r);
//左子树
// 前序遍历的左子树 起始位置：pstart + 1 结束位置：pstart + (position - 1 -istart + 1)
// 中序遍历的左子树 起始位置:istart 结束位置 position -1
root.left = buildTree(preorder,pstart + 1,pstart + (position - 1 -istart + 1),inorder,istart,position-1);
// 右子树
// 前序遍历的右子树 起始位置 pstart + (position - 1 -istart + 1) + 1 结束位置：pend
// 中序遍历的右子树 起始位置:position + 1 结束位置：iend
root.right = buildTree(preorder,pstart + (position - 1 -istart + 1) + 1,pend,inorder,position + 1,iend);
return root;
} }