[Algorithm] Flatten Binary Tree to Doubly Linked List As Postorder

Postorder反而是这些里面最简单的，因为后序的话不需要考虑备份子节点，代码如下：

	package kimi;
	import java.util.Stack;
	public class flattenToDoublyLinkedListAsPostorder {
	private TreeNode head = null;
	private TreeNode tail = null;
	public TreeNode flattenRecursively(TreeNode root) {
	postOrder(root);
	return head;
	}
	private void postOrder(TreeNode node) {
	if (node == null)
	return;
	postOrder(node.left);
	postOrder(node.right);
	if(head == null) {
	head = node;
	head.left = null;
	tail = node;
	tail.right = null;
	} else {
	tail.right = node;
	node.left = tail;
	tail = tail.right;
	tail.right = null;
	}
	}
	public TreeNode flattenIteratively(TreeNode root) {
	if (root == null)
	return null;
	Stack<TreeNode> stack = new Stack<TreeNode>();
	TreeNode pre = null, head = null, tail = null;
	stack.push(root);
	while(!stack.isEmpty()) {
	TreeNode curr = stack.peek();
	if (isLeaf(curr) || (pre != null && (pre == curr.left || pre == curr.right))) {
	stack.pop();
	if (head == null) {
	head = curr;
	tail = curr;
	head.left = null;
	head.right = null;
	} else {
	tail.right = curr;
	curr.left = tail;
	tail = tail.right;
	tail.right = null;
	}
	pre = curr;
	}
	else {
	if (curr.right != null)
	stack.push(curr.right);
	if (curr.left != null)
	stack.push(curr.left);
	}
	}
	return head;
	}
	private boolean isLeaf(TreeNode node) {
	return node.left == null && node.right == null;
	}
	//for test use, serialize doubly linked list
	public String serialize(TreeNode head) {
	String res = "";
	while(head != null) {
	res += "<-";
	res += head.val;
	res += "->";
	head = head.right;
	}
	return res;
	}
	public static void main(String[] args) {
	test1();
	test2();
	test3();
	test4();
	test5();
	test6();
	}
	//test cases
	private static void test1() {
	TreeNode root = new TreeNode(1);
	flattenToDoublyLinkedListAsPostorder f = new flattenToDoublyLinkedListAsPostorder();
	if (f.serialize(f.flattenRecursively(root)).equals("<-1->"))
	System.out.println("test case 1 passed!");
	else
	System.out.println("test case 1 failed!");
	}
	private static void test2() {
	TreeNode root = new TreeNode(1);
	flattenToDoublyLinkedListAsPostorder f = new flattenToDoublyLinkedListAsPostorder();
	if (f.serialize(f.flattenIteratively(root)).equals("<-1->"))
	System.out.println("test case 2 passed!");
	else
	System.out.println("test case 2 failed!");
	}
	private static void test3() {
	TreeNode root = new TreeNode(1);
	root.left = new TreeNode(2);
	root.right = new TreeNode(3);
	root.left.right = new TreeNode(4);
	root.right.right = new TreeNode(5);
	root.right.right.left = new TreeNode(6);
	flattenToDoublyLinkedListAsPostorder f = new flattenToDoublyLinkedListAsPostorder();
	if (f.serialize(f.flattenRecursively(root)).equals("<-4-><-2-><-6-><-5-><-3-><-1->"))
	System.out.println("test case 3 passed!");
	else
	System.out.println("test case 3 failed!");
	}
	private static void test4() {
	TreeNode root = new TreeNode(1);
	root.left = new TreeNode(2);
	root.right = new TreeNode(3);
	root.left.right = new TreeNode(4);
	root.right.right = new TreeNode(5);
	root.right.right.left = new TreeNode(6);
	flattenToDoublyLinkedListAsPostorder f = new flattenToDoublyLinkedListAsPostorder();
	if (f.serialize(f.flattenIteratively(root)).equals("<-4-><-2-><-6-><-5-><-3-><-1->"))
	System.out.println("test case 4 passed!");
	else
	System.out.println("test case 4 failed!");
	}
	private static void test5() {
	TreeNode root = new TreeNode(3);
	root.left = new TreeNode(7);
	root.right = new TreeNode(6);
	root.left.left = new TreeNode(4);
	root.left.right = new TreeNode(2);
	root.right.right = new TreeNode(5);
	root.left.left.left = new TreeNode(12);
	root.left.left.left.right = new TreeNode(0);
	root.left.right.right = new TreeNode(10);
	root.right.right.left = new TreeNode(8);
	root.right.right.right = new TreeNode(9);
	root.right.right.left.left = new TreeNode(17);
	root.right.right.right.right= new TreeNode(20);
	flattenToDoublyLinkedListAsPostorder f = new flattenToDoublyLinkedListAsPostorder();
	if (f.serialize(f.flattenRecursively(root)).equals("<-0-><-12-><-4-><-10-><-2-><-7-><-17-><-8-><-20-><-9-><-5-><-6-><-3->"))
	System.out.println("test case 5 passed!");
	else
	System.out.println("test case 5 failed!");
	}
	private static void test6() {
	TreeNode root = new TreeNode(3);
	root.left = new TreeNode(7);
	root.right = new TreeNode(6);
	root.left.left = new TreeNode(4);
	root.left.right = new TreeNode(2);
	root.right.right = new TreeNode(5);
	root.left.left.left = new TreeNode(12);
	root.left.left.left.right = new TreeNode(0);
	root.left.right.right = new TreeNode(10);
	root.right.right.left = new TreeNode(8);
	root.right.right.right = new TreeNode(9);
	root.right.right.left.left = new TreeNode(17);
	root.right.right.right.right= new TreeNode(20);
	flattenToDoublyLinkedListAsPostorder f = new flattenToDoublyLinkedListAsPostorder();
	if (f.serialize(f.flattenIteratively(root)).equals("<-0-><-12-><-4-><-10-><-2-><-7-><-17-><-8-><-20-><-9-><-5-><-6-><-3->"))
	System.out.println("test case 6 passed!");
	else
	System.out.println("test case 6 failed!");
	}
	}

view raw flattenToDoublyLinkedListAsPostorder.java hosted with ❤ by GitHub

如果要constant space的话，类似morris遍历的方法，在每次回收节点的时候，回收的是一个链表上的所有节点，我们只需把链表reverse一样，按照要求连接好，然后连接点之前已经构好的list的末尾就可以了。