Flatten Binary Tree to Linked List

问题明显递归操作比较简单，我们看下草图：

紫色矩形表示进行了相同处理后的结果，在链接root和左子树的时候是可以直接操作的，但是我们这么去链接左子树和右子树呢？应该是左子树中最后的那个结点跟右子树的root链接，所以我们需要去找到左子树的最后(最右)那个非空结点。

//code

class Solution {
public:
	TreeNode *&link(TreeNode *&root)
	{
		if(root == NULL || root->left == NULL && root->right == NULL) 
			return root;
		TreeNode *root_left = NULL;
		TreeNode *root_right = NULL;
		root_left = link(root->left);
		root_right = link(root->right);
		if(root_left != NULL)
		{
			TreeNode *tail = root_left;
			//find the last one of root->left.
			while(tail->right) tail = tail->right;
			tail->right = root_right;
		}
		else
			root_left = root_right;
		root->right = root_left;
		root->left = NULL;
		return root;
	}
	void flatten(TreeNode *root) {
		if(root == NULL) return;
		root = link(root);
	}
};