897. Increasing Order Search Tree

Leetcode link

解题思路

要把一个 BST 转变为单边递增的树，第一个想到的方法就是深度优先遍历的中序遍历，为了提高效率，最好是利用题目给的节点去做原地修改。

C++

class Solution {
 public:
  TreeNode* cur;
  void dfs(TreeNode* node) {
    if (node == nullptr) {
      return;
    }
    dfs(node->left);
    node->left = nullptr;
    cur->right = node;
    cur = cur->right;
    dfs(node->right);
  }

  TreeNode* increasingBST(TreeNode* root) {
    TreeNode* res = new TreeNode();
    cur = res;
    dfs(root);
    return res->right;
  }
};

Javascript

var increasingBST = function(root) {
    let res = new TreeNode();
    let cur = res;

    let dfs = (node)=>{
        if(!node) {
            return;
        }
        dfs(node.left);
        node.left = null;
        cur.right = node;
        cur = cur.right;
        dfs(node.right);
    }

    dfs(root);
    return res.right;
};