题目链接：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

Hints:

If you notice carefully in the flattened tree, each node’s right child points to the next node of a pre-order traversal.

这道题的要求是将二叉树转化成链表。可以注意到，每个节点的right就是指向前序遍历的下一节点。

这道题就是要求前序遍历，然后将每个节点的right指针指向下一节点即可。用栈记录每个节点的右子树，如果左子树不为NULL，者将其复制给right指针，同时将left置NULL；如果左子树为空，则需要从栈顶取元素，并赋值给right指针即可。

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution 
{
public:
    void flatten(TreeNode *root) 
    {
        TreeNode *p = root;
        stack<TreeNode *> s;
        while(p != NULL)
        {
            if(p -> right != NULL)
                s.push(p -> right);
            
            if(p -> left != NULL)
            {
                p -> right = p -> left;
                p -> left = NULL;
            }
            else if(!s.empty())
            {
                p -> right = s.top();
                s.pop();
            }
            
            p = p -> right;
        }
    }
};