【ACWing】49. 二叉搜索树与双向链表

https://www.acwing.com/problem/content/description/87/

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
注意：
需要返回双向链表最左侧的节点。

数据范围：
树中节点数量 [ 0 , 500 ] [0,500] [0,500]。

直接中序遍历一遍即可。代码如下：

#include 
using namespace std;

struct TreeNode {
  int val;
  TreeNode *left, *right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
  TreeNode* convert(TreeNode* root) {
    stack stk;
    auto dummy = new TreeNode(0), prev = dummy;
    while (stk.size() || root) {
      while (root) {
        stk.push(root);
        root = root->left;
      }

      root = stk.top(); stk.pop();
      prev->right = root;
      root->left = prev;
      prev = prev->right;

      root = root->right;
    }

    root = dummy->right;
    // 把dummy和最终答案断开
    dummy->right = nullptr;
    if (root) root->left = nullptr;
    return root;
  }
};

时间复杂度 O ( n ) O(n) O(n)，空间 O ( h ) O(h) O(h)。