学步园

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

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
    	TreeNode* tail=root;
		_flatten(root,tail);
    }
	void _flatten(TreeNode*& root,TreeNode*& tail)
	{
		if( !root )
			return;
		TreeNode* lhead=root->left,*ltail=root->left;
		_flatten(lhead,ltail);
		TreeNode* rhead=root->right,*rtail=root->right;
		_flatten(rhead,rtail);
		if ( lhead )
		{
			tail->right=lhead;
			tail=ltail;
		}
		if ( rhead )
		{
			tail->right=rhead;
			tail=rtail;
		}
		root->left=tail->right=NULL;
	}
};