[LeetCode] Flatten Binary Tree to Linked List

Binary Tree按preorder的顺序展开成Linkedlist，right是next指针，left指向null就行。首先递归的做法，preorder的顺序递归，维护展开list的head和tail，每次访问tree的节点的时候把tail的next连向当前node，tail = tail.next。注意链接当前node的时候要改变node的左右指针，所以注意先备份左右子节点，然后继续递归的时候传入备份节点，递归版本如下：

	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	public class Solution {
	private TreeNode head = null;
	private TreeNode tail = null;
	public void flatten(TreeNode root) {
	preOrder(root);
	return;
	}
	private void preOrder(TreeNode node) {
	if (node == null)
	return;
	TreeNode leftCopy = 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 = null;
	tail = tail.right;
	tail.right = null;
	}
	preOrder(leftCopy);
	preOrder(rightCopy);
	}
	}

view raw flatten binary tree to linked list as preorder recursive.java hosted with ❤ by GitHub

迭代的做法要参考迭代遍历tree的版本，注意这里我们再循环的时候可以备份左子节点，但是要备份右子节点的话还是得维护一个stack，stack里的每一个元素对应path里每一个元素的右子结点，这样每次找后继的节点的时候也能找到后继节点的原右子结点，因为现在后继结点的右子结点已经改变了。代码如下：

	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	public class Solution {
	public void flatten(TreeNode root) {
	TreeNode curr = root, head = null, tail = null;
	Stack<TreeNode> path = new Stack<TreeNode>();
	Stack<TreeNode> rightChildren = new Stack<TreeNode>();
	while (!path.isEmpty() || curr != null) {
	while (curr != null) {
	path.push(curr);
	rightChildren.push(curr.right);
	TreeNode leftCopy = curr.left;
	if (head == null) {
	head = curr;
	tail = curr;
	head.left = null;
	head.right = null;
	} else {
	tail.right = curr;
	curr.left = null;
	tail = tail.right;
	tail.right = null;
	}
	curr = leftCopy;
	}
	path.pop();
	curr = rightChildren.pop();
	}
	return;
	}
	}

view raw flatten binary tree to linked list as preorder iterative.java hosted with ❤ by GitHub

Follow up：Flatten Binary Tree to Doubly-Linkedlist As Preorder，Flatten Binary Tree to Doubly-Linkedlist As Inorder，Flatten Binary Tree to Doubly-Linkedlist As Postorder