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.

 

C++代码如下：

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;//Definition for binary treestruct TreeNode{    int val;    TreeNode *left;    TreeNode *right;    TreeNode(int x) : val(x), left(NULL), right(NULL) {}};class Solution{public:    void flatten(TreeNode *root)    {        if(root==NULL)            return;        vector
          
            vec;        preorder(root,vec);        TreeNode *tmp=root;        size_t i;        for(i=1; i
           
            left=NULL; tmp->right=vec[i]; tmp=tmp->right; } tmp->left=tmp->right=NULL; } void preorder(TreeNode *root,vector
            
              &vec) { stack
             
               s; while(root||!s.empty()) { while(root) { vec.push_back(root); s.push(root); root=root->left; } if(!s.empty()) { root=s.top(); s.pop(); root=root->right; } } } void createTree(TreeNode *&root) { int i; cin>>i; if(i!=0) { root=new TreeNode(i); if(root==NULL) return; createTree(root->left); createTree(root->right); } }};int main(){ Solution s; TreeNode *root; s.createTree(root); s.flatten(root); while(root) { cout<
              
               val<<" "; root=root->right; }}
              
             
            
           
          
         
        
       
      

运行结果：

提交到leetcode时，一直报错，开始不太了解，后来才发现是因为左指针一直没有设为NULL.

class Solution {public:    void flatten(TreeNode *root)    {        if(root==NULL)            return;        vector
      
        vec;        preorder(root,vec);        TreeNode *tmp=root;        size_t i;        for(i=1; i
       
        right=vec[i];            tmp=tmp->right;        }        tmp->right=NULL;    }    void preorder(TreeNode *root,vector
        
          &vec)    {        stack
         
           s;        while(root||!s.empty())        {            while(root)            {                vec.push_back(root);                s.push(root);                root=root->left;            }            if(!s.empty())            {                root=s.top();                s.pop();                root=root->right;            }        }    }    void createTree(TreeNode *&root)    {        int i;        cin>>i;        if(i!=0)        {            root=new TreeNode(i);            if(root==NULL)                return;            createTree(root->left);            createTree(root->right);        }    }};
         
        
       
      

注意，最后的指针哪些该设置为空。