LeetCode——Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.
For example, Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

Hints:
If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.
原題リンク:https://oj.leetcode.com/problems/flatten-binary-tree-to-linked-list/
タイトル:二叉木を与え、前の順序で平成のチェーンテーブルを展示します.
考え方:再帰処理.右のサブツリーを左のサブツリーの後に置き、左のサブツリーを空にします.

	public void flatten(TreeNode root) {
		if(root == null)
			return;
		flatten(root.left);
		flatten(root.right);
		TreeNode tmp = root;
		if(tmp.left == null)
			return;
		else
			tmp = tmp.left;
		while(tmp.right != null)
			tmp = tmp.right;
		tmp.right = root.right;
		root.right = root.left;
		root.left = null;
	}
    // Definition for binary tree
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

も同様ですが、再帰的ではありません.

	public void flatten(TreeNode root){
		while(root != null){
			if(root.left != null){
				TreeNode tmp = root.left;
				while(tmp.right != null)
					tmp = tmp.right;
				tmp.right = root.right;
				root.right = root.left;
				root.left = null;
			}
			root = root.right;
		}
	}

reference : http://blog.csdn.net/perfect8886/article/details/20000083