题目描述

给定一个树，按中序遍历重新排列树，使树中最左边的结点现在是树的根，并且每个结点没有左子结点，只有一个右子结点。

样例

输入：[5,3,6,2,4,null,8,1,null,null,null,7,9]

       5
      / \
    3    6
   / \    \
  2   4    8
 /        / \ 
1        7   9

输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

 1
  \
   2
    \
     3
      \
       4
        \
         5
          \
           6
            \
             7
              \
               8
                \
                 9  

注意

• 给定树中的结点数介于 1 和 100 之间。
• 每个结点都有一个从 0 到 1000 范围内的唯一整数值。

算法

(递归) $O(n)$

1. 定义递归函数 solve，参数为指针类型的引用，返回值为当前结点的最右侧结点。
2. solve (rt) 的目标是将 rt 为根的子树重排列，并返回排列后最右侧结点。
3. 如果 rt 的左右儿子都是空，则返回 rt；
4. 如果 rt 的左儿子为空，则返回 solve(rt -> right)；
5. 否则，solve(rt -> left)，并取出左儿子的 right_most，将 right_most 的右儿子置为 rt，记录 rt 的左儿子后将 rt 的左儿子变为空，然后将 rt 自身变为 rt 的左儿子；最后返回原来 solve(原来 rt 的右儿子，即 (right_most -> right)。

时间复杂度

• 每个结点仅被访问一次，故时间复杂度为 $O(n)$。

空间复杂度

• 需要系统提供栈空间，大小为树的深度，故空间复杂度为 $O(H)$。

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:

    TreeNode* solve(TreeNode* &rt) {
        if (rt -> left == nullptr && rt -> right == nullptr)
            return rt;

        if (rt -> left == nullptr && rt -> right != nullptr)
            return solve(rt -> right);

        TreeNode *right_most = solve(rt -> left);
        TreeNode *left = rt -> left;
        right_most -> right = rt;
        rt -> left = nullptr;
        rt = left;
        return solve(right_most -> right);
    }

    TreeNode* increasingBST(TreeNode* root) {
        solve(root);
        return root;
    }
};