题目

题目来源：力扣（LeetCode

二叉树数据结构TreeNode可用来表示单向链表（其中left置空，right为下一个链表节点）。实现一个方法，把二叉搜索树转换为单向链表，要求依然符合二叉搜索树的性质，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。

返回转换后的单向链表的头节点。

注意：本题相对原题稍作改动

示例：

输入： [4,2,5,1,3,null,6,0]
输出： [0,null,1,null,2,null,3,null,4,null,5,null,6]

思路分析

二叉搜索树中序遍历结果为从小到大顺序，每次保存上一次中序遍历的结点，让上一个结点的右子树指向当前结点，并把当前结点左子树置空。

具体地：

  1. 新建一个节点
  2. 中序遍历二叉搜索树
  3. 边遍历边操作一次，改变一次位置
  4. 操作一次有3个步骤：
    1. 当前根节点的左节点赋为null；
    2. 上一个节点的右节点指向当前节点；
    3. 更新上一个节点，以便下次操作
  5. 最后返回新建节点的右节点
  1. /**
  2.  * Definition for a binary tree node.
  3.  * function TreeNode(val) {
  4.  *     this.val = val;
  5.  *     this.left = this.right = null;
  6.  * }
  7.  */
  8. /**
  9.  * @param {TreeNode} root
  10.  * @return {TreeNode}
  11.  */
  12. // 1.将当前根节点的左节点 赋值为null；
  13. // 2.上一个节点的右节点指向当前节点
  14. // 3.更新上一个节点，方便我们下一步操作
  15. var convertBiNode = function (root) {
  16.   //新建一个节点，作为初始空节点的上一个节点
  17.   let preNode = new TreeNode(0);
  18.   const res = preNode;
  19.   const inOrder = root => {
  20.     if (!root) return null;
  21.     inOrder(root.left);
  22.     // 将当前根节点的左节点 赋值为null；
  23.     root.left = null;
  24.     // 上一个节点的右节点指向当前节点
  25.     preNode.right = root;
  26.     // 更新上一个节点，方便我们下一步操作
  27.     preNode = root;
  28.     inOrder(root.right);
  29.   }
  30.   inOrder(root);
  31.   return res.right;
  32. };