已知一棵二叉搜索树的前序遍历序列,求二叉搜索树的中序遍历序列
例:
input : 5 3 2 4 7 6
output : 2 3 4 5 6 7
思路1.最简单的方法是直接排序数组,因为二叉搜索树的中序遍历是有序的.缺点在于排序的时间复杂度最低也是O(nlogn),并没有利用前序遍历的特点.
2.前序遍历的第一个节点一定是根节点,然后根据二叉搜索树左子树小于根节点,右子树大于根节点的特点,将数组分为三部分, 根节点 - wydgs , 然后对于左右子树分别递归的采用此思想分解.
代码 public int[] getMidTravel(int[] a){ int[] result = new int[a.length]; getMidTravel(a,0,a.length-1,result,0); return result; } public void getMidTravel(int[] a,int begin,int end,int[] result,int offset){ if(begin>end) return; if(begin==end){ result[begin+offset] = a[begin]; return; } int i=begin+1; for(;i<a.length&&a[i]<a[begin];i++); result[i-1+offset] = a[begin]; getMidTravel(a,begin+1,i-1,result,offset-1); getMidTravel(a,i,end,result,offset); }