java比较好懂的方法-通过先序中序遍历还原二叉树

前序：ABCDEF

中序：CBAEDF

求原来的二叉树

前序：根左右

中序：左根右

根据前序和中序还原二叉树：

思路：根据前序知道二叉树的根包括各个子树的根，然后再在中序里面找到根的那个，前面的都是左子树，而后面的都是右子树，然后用递归的思想再处理每个子树的那部分。思路还是一样的。

书上和网上的教程非要用数组然后用下标来分割数组表示左右子树的结点,看的人眼花缭乱的，写起来的时候也是经常控制不好下标的变化，虽然用下标好处多多，但是初学者会很不容易理解，做题的时候也会经常出现笔误导致多次调试。既然要表示左右子树的结点而且结点经常变动为什么不直接用在这方面更加擅长的链表呢？？

具体实现方法看代码里面的注释：

public TreeNode buildTree(int[] preorder, int[] inorder) {

/**

* 转换数组为链表便于使用

*/

LinkedList pre=new LinkedList(),ino=new LinkedList();

for (int i : preorder) {

pre.addLast(i);

}

for (int i : inorder) {

ino.addLast(i);

}

return plus(pre, ino);

}

private TreeNode plus(LinkedList preorder,LinkedList inorder){

//如果结点数量为空表示当前子树为null

if (preorder.size()==0)

return null;

//当前结点

TreeNode root=new TreeNode(preorder.get(0));

LinkedList pl=new LinkedList();

LinkedList il=new LinkedList();

//将要构造的左子树的对应结点找出来

while (true){

int i=inorder.pollFirst();

pl.addLast(preorder.pollFirst());

il.addLast(i);

//如果i是中序的当前结点证明左子树的结点已经找到完了--preorder,inorder剩下的就是右子树的结点

if (i==root.val){

break;

}

}

//剔除当前结点

pl.pollFirst();

il.pollLast();

//递归寻找当前结点的两个子树

root.left=plus(pl,il);

root.right=plus(preorder, inorder);

return root;

}