给你一棵二叉搜索树，请你 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。

示例

示例 1：

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

示例 2：

输入：root = [5,1,7]
输出：[1,null,5,null,7]

题解

中序遍历二叉树，储存每个节点，遍历节点将它们连接

  1. /**
  2.  * Definition for a binary tree node.
  3.  * function TreeNode(val, left, right) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.left = (left===undefined ? null : left)
  6.  *     this.right = (right===undefined ? null : right)
  7.  * }
  8.  */
  9. /**
  10.  * @param {TreeNode} root
  11.  * @return {TreeNode}
  12.  */
  13. var increasingBST = function(root) {
  14.     const stack = []
  15.     const run = node => {
  16.         if (node.left) {
  17.             run(node.left)
  18.         }
  20.         stack.push(node)
  22.         if (node.right) {
  23.             run(node.right)
  24.         }
  25.     }
  26.     run(root)
  28.     const tree = stack[0]
  29.     tree.left = null
  32.     for (let i = 1; i < stack.length; i++) {
  33.         stack[i].left = null
  34.         stack[i - 1].right = stack[i]
  35.     }
  36.     return tree
  37. };

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/increasing-order-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。