一、还原二叉树
先序、中序
后序、中序
二、先序和中序的还原
---------------------------------------------- A / \ B C / \ / \ D E G F ----------------------------------------------先序遍历结果:ABDECGF
中序遍历结果:DBEAGCF
先序中每个树的节点 左子树 相邻的节点但是要在先序中寻找的
右子树 先序中树的节点距离+先序中的位置 下一个就是右子树
例如：B 在先序 D [B] E
B的下一个节点在左子树木中D可以找的到
右子树木中序B距离1 那么右子树在先序中+这个距离的下一个
/** * * 先序 中序 */public class ConstructBinaryTree { public TreeNode buildTree(int[] preorder, int[] inorder) { return findTree(preorder,0,preorder.length-1,inorder,0,inorder.length-1); } public TreeNode findTree(int[] preorder,int preStart,int preEnd,int[] inorder,int inIndex,int inEnd){ if(preStart>=preorder.length||inIndex>inEnd) return null; int i=inIndex; while(i<=inEnd){ if(preorder[preStart]==inorder[i++]) break; } TreeNode tn=new TreeNode(preorder[preStart]); tn.left=findTree(preorder,preStart+1,preEnd,inorder,inIndex,i-2); tn.right=findTree(preorder,preStart+i-inIndex,preEnd,inorder,i,inEnd); return tn; } public static void main(String[] args) { ConstructBinaryTree cbt=new ConstructBinaryTree(); cbt.buildTree(new int[]{1,2,3}, new int[]{1,2,3}); }}
三、后序和先序的还原
后序遍历结果:DEBGFCA
中序遍历结果:DBEAGCF
反过来就是啦 右子树就是左边的
左子树就是 左边开始+距离-1
/** * * 后序 中序 */public class ConstructBinaryTreeTwo { public TreeNode buildTree(int[] inorder, int[] postorder) { return findTree(postorder,postorder.length-1,0,inorder,0,inorder.length-1); } public TreeNode findTree(int[] postorder,int postEnd,int postStart,int[] inorder,int inIndex,int inEnd){ if(postEnd inEnd) return null; int i=inIndex; while(i<=inEnd){ if(postorder[postEnd]==inorder[i++]) break; } TreeNode tn=new TreeNode(postorder[postEnd]); tn.left=findTree(postorder,postStart+(i-inIndex-1),postStart,inorder,inIndex,i-2); tn.right=findTree(postorder,postEnd-1,postStart+(i-inIndex-1),inorder,i,inEnd); return tn;} public static void main(String[] args) { ConstructBinaryTreeTwo cbt=new ConstructBinaryTreeTwo(); cbt.buildTree(new int[]{1,3,2}, new int[]{3,2,1}); }}