1 迭代，重要关系  

p->right = s.top();

 

1 class flat{ 2     public: 3         void flatten(TreeNode* root) { 4             if (root == NULL) return; 5             stack
     
       s; 6             s.push(root); 7             while (!s.empty()) { 8                 TreeNode *p = s.top(); 9                 s.pop();10                 if (p->right)11                     s.push(p->right);12                 if (p->left)13                     s.push(p->left);14                 p->left = NULL;15                 if (!s.empty())16                     p->right = s.top();17             }18         }19 };
     

 

2 递归 

思路：

1 搞定左边

2 搞定右边

3 将左边的插入到root 和right中间

　　3.1 找到左边的最后一个节点 left_most

　　3.2 left_most->right = root->right;

　　3.3 root->right = left

 

1 class flat{ 2     public: 3             void  flatten_rec(TreeNode* root) { 4             if (root == NULL) return; 5             if(root->left == NULL && root->right == NULL) 6                 return ; 7  8             flatten_rec(root->left); 9             flatten_rec(root->right);10             11             TreeNode * left_most = root->left;12             while(left_most && left_most->right)13             {14                 left_most = left_most->right;15             }16             if(root->left != NULL)17             {18                 left_most->right = root->right;19                 root->right = root->left;20             }21 22             root->left = NULL;23             return ;24 25         }26 };