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

思路：此题为前序遍历。 可以用迭代也可以用stack。stack的方法更直观一些。

代码：

1 class Solution {
 2 public:
 3     void flatten(TreeNode *root) {
 4         // Start typing your C/C++ solution below
 5         // DO NOT write int main() function
 6         if (root == NULL) return;
 7         stack<TreeNode*> stk;
 8         stk.push(root);
 9         TreeNode np(0);
10         TreeNode* ptr = &np;
11         while(!stk.empty())
12         {
13             TreeNode* p = stk.top();
14             stk.pop();
15             if(p != NULL)
16             {
17                 stk.push(p->right);
18                 stk.push(p->left);
19                 
20                 ptr->right = p;
21                 ptr = p;
22                 ptr->left = NULL;
23             }
24         }
25     }
26 };

1 class Solution {
 2 public:
 3     void flatten(TreeNode *root) {
 4         // Start typing your C/C++ solution below
 5         // DO NOT write int main() function
 6         if (root == NULL) return;
 7         //1.flat the left subtree
 8         if (root->left)
 9             flatten(root->left);
10         //2.flatten the right subtree
11         if (root->right)
12             flatten(root->right);
13         //3.if no left return
14         if (NULL == root->left)
15             return;
16         //4.insert left sub tree between root and root->right
17         //4.1.find the last node in left
18         TreeNode ** ptn = & (root->left->right);
19         while (*ptn)
20             ptn = & ((*ptn)->right);
21         //4.2.connect right sub tree after left sub tree
22         *ptn = root->right;
23         //4.3.move left sub tree to the root's right sub tree
24         root->right = root->left;
25         root->left = NULL;
26         
27     }
28 };

原文链接: https://www.cnblogs.com/tanghulu321/archive/2013/05/07/3064039.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍