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

在preorder递归和迭代版本做略微修改就行了。迭代版本我们第二次访问节点的时候调整左右指针，注意只要备份右指针，然后去到原右子结点。左子节点不需要备份因为之后我们不会去左子树了。递归版本是类似的，只需备份右子结点，代码如下：

	public class flattenToDoublyLinkedListAsInorder {
	private TreeNode head = null;
	private TreeNode tail = null;
	public TreeNode flattenRecursively(TreeNode root) {
	InOrder(root);
	return head;
	}
	private void InOrder(TreeNode node) {
	if (node == null)
	return;
	InOrder(node.left);
	TreeNode rightCopy = 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;
	}
	InOrder(rightCopy);
	}
	public TreeNode flattenIteratively(TreeNode root) {
	TreeNode curr = root, head = null, tail = null;
	Stack<TreeNode> path = new Stack<TreeNode>();
	while (!path.isEmpty() || curr != null) {
	while (curr != null) {
	path.push(curr);
	curr = curr.left;
	}
	curr = path.pop();
	TreeNode rightCopy = curr.right;
	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;
	}
	curr = rightCopy;
	}
	return head;
	}
	//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);
	flattenToDoublyLinkedListAsInorder f = new flattenToDoublyLinkedListAsInorder();
	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);
	flattenToDoublyLinkedListAsInorder f = new flattenToDoublyLinkedListAsInorder();
	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);
	flattenToDoublyLinkedListAsInorder f = new flattenToDoublyLinkedListAsInorder();
	if (f.serialize(f.flattenRecursively(root)).equals("<-2-><-4-><-1-><-3-><-6-><-5->"))
	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);
	flattenToDoublyLinkedListAsInorder f = new flattenToDoublyLinkedListAsInorder();
	if (f.serialize(f.flattenIteratively(root)).equals("<-2-><-4-><-1-><-3-><-6-><-5->"))
	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);
	flattenToDoublyLinkedListAsInorder f = new flattenToDoublyLinkedListAsInorder();
	if (f.serialize(f.flattenRecursively(root)).equals("<-12-><-0-><-4-><-7-><-2-><-10-><-3-><-6-><-17-><-8-><-5-><-9-><-20->"))
	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);
	flattenToDoublyLinkedListAsInorder f = new flattenToDoublyLinkedListAsInorder();
	if (f.serialize(f.flattenIteratively(root)).equals("<-12-><-0-><-4-><-7-><-2-><-10-><-3-><-6-><-17-><-8-><-5-><-9-><-20->"))
	System.out.println("test case 6 passed!");
	else
	System.out.println("test case 6 failed!");
	}
	}

view raw flattenToDoublyLinkedListAsInorder.java hosted with ❤ by GitHub

如果要求是constant space的话，用类似morris遍历的方法，第一次访问的时候把前驱结点的右指针链接到当前节点上，第二次访问的时候把节点链接到list上去，记得备份右子结点。然后去到原右子结点。