202

问答题 202 /376

算法题,给前序和中序,求出二叉树

参考答案

参考回答:

class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class TestRecoverBinaryTree {
public TreeNode reConstructBinaryTree(int [] preOrder,int [] inOrder)
{
int pLen = preOrder.length;
int iLen = inOrder.length;
if(pLen==0 && iLen==0)
{
return null;
}
return  btConstruct( preOrder, inOrder, 0, pLen-1,0, iLen-1);
}

//构建方法,pStart和pEnd分别是前序遍历序列数组的第一个元素和最后一个元素;

//iStart和iEnd分别是中序遍历序列数组的第一个元素和最后一个元素。

public TreeNode btConstruct(int[] preOrder, int[] inOrder, int pStart, int pEnd,int iStart,int iEnd)

{

//建立根节点

TreeNode tree = new TreeNode(preOrder[pStart]);
tree.left = null;
tree.right = null;
if(pStart == pEnd && iStart == iEnd)
{
return tree;
}
int root = 0;

//找中序遍历中的根节点

for(root=iStart; root<iEnd; root++)
{
if(preOrder[pStart] == inOrder[root])
{
break;
}
}

//划分左右子树

int leftLength = root - iStart;//左子树

int rightLength = iEnd - root;//右子树

//遍历左子树

if(leftLength>0)
{
tree.left = btConstruct(preOrder, inOrder,  pStart+1,  pStart+leftLength, iStart, root-1);
}

//遍历右子树

if(rightLength>0)
{
tree.right = btConstruct(preOrder, inOrder,  pStart+leftLength+1,  pEnd, root+1, iEnd);
}
return tree;
}
}