题目描述

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

示例:

输入：[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

题目分析

使用递归中序储存节点至vector中, 后重新构建树.

源码

class Solution {
public:
    vector<TreeNode*> nodes;
    void iterate(TreeNode* root) {
        if(root == NULL) { // 如果节点为空则返回
            return;
        }else { // 节点不为空
            iterate(root->left); // 中序遍历左子树储存节点
            nodes.push_back(root); // 储存本节点
            iterate(root->right); // 中序遍历右子树储存节点
            return;
        }
    }

    TreeNode* increasingBST(TreeNode* root) {
        iterate(root); // 
        TreeNode* res = nodes[0];
        res->left = NULL;
        TreeNode* it = res;
        for(int i=1; i<nodes.size(); ++i) {
            it->right = nodes[i];
            it->left = NULL;
            it = it->right;
        }
        it->left = NULL;
        return res;
    }
};