Create Postorder

Leave a comment

December 14, 2016 by oneOokay

做完Construct binary tree之后写出的一个recursive的算法:

  • 同样的以preorder来遍历
  • helper method传入preindex,inStart和inEnd
  • 从postorder的最后一个元素往前构造(postorder: LEFT->RIGHT->ROOT)所以应该先对它的右子树进行recursion,先把它右儿子放到postorder里面去。这里是与之前construct binary tree不同的地方。
  • 一个postIndex来控制当前的helper把值放到postorder的哪个位置。这个不能放在helper 里面。
public class createPostOrder {
	private static int[] post;
	private static int[] pre;
	private static int[] in;
	private static int postIndex;
	public static int[] doIt(int[] preorder, int[] inorder){
		if (preorder.length == 0 || inorder.length == 0){
			return null;
		}
		pre = preorder;
		in = inorder;
		post = new int[preorder.length];
		postIndex = post.length - 1;
		helper(0, 0, inorder.length - 1);
		return post;
	}
	
	private static void helper(int preIndex, int inStart, int inEnd){
		if (preIndex > pre.length || inStart > inEnd){
			return;
		}
		post[postIndex--] = pre[preIndex];
		int index = 0;
		for (int i = inStart; i <= inEnd; i ++){
			if (in[i] == pre[preIndex]){
				index = i;
				break;
			}
		}
		helper(preIndex + index - inStart + 1, index + 1, inEnd);
		helper(preIndex + 1, inStart, index - 1);
	}
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: