算法题,给前序和中序,求出二叉树
参考回答:
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; } }