题目描述

给定一棵二叉树，请使用原地算法将它转化成一条链。
二叉树中序遍历的顺序可以改变。

样例

给定的二叉树如下所示：

    1
   / \
  2   5
 / \   \
3   4   6

一种可能的展平方案是：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

算法

(树的遍历) $O(n)$

这道题目考察了对树和链表的操作。

我们先定义右链：指一棵子树最右侧的路径。
我们从根节点开始迭代，每次将当前节点的左子树的右链，插入当前节点的右链，如下所示：

1.  1
   / \
  2   5
 / \   \
3   4   6

2.  1
     \
      2
     / \
    3   4
         \
          5
           \
            6

3.  1
     \
      2
       \
        3
         \
          4
           \
            5
             \
              6

时间复杂度分析：虽然有两重循环，但外层循环会将所有节点遍历一次，内层循环会将除了根节点之外的其他内部结点的右链遍历一次，所以每个节点最多被遍历两次，所以时间复杂度是 $O(n)$。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode *now = root;
        while (now)
        {
            if (now->left)
            {
                TreeNode *p = now->left;
                while (p->right) p = p->right;
                p->right = now->right;
                now->right = now->left;
                now->left = 0;
            }
            now = now->right;
        }
    }
};