1. 题目描述

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。

2. 思路分析

在搜索二叉树中,左子结点的值总是小于父结点的值,右子结点的值总是大于父结点的值。因此我们在转换成排序双向链表时,原先指向左子结点的指针调整为链表中指向前一个结点的指针,原先指向右子结点的指针调整为链表中指向后一个结点指针

因为要遍历树,所以要选取遍历算法。为了保证遍历的有序性,采用中序遍历。在 convertNode 函数实现中,注意 lastNodeInList 语意,剩下的按照思路写出来即可。

3. 代码实现

class TreeNode {
  constructor(value, left = null, right = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

/**
 * 将node和左右子树转化为双向链表
 * @param {TreeNode} node 待转化的节点
 * @param {TreeNode} lastNodeInList 已转换好的双向链表的尾结点
 */
function convertNode(node, lastNodeInList = null) {
  if (!node) {
    return null;
  }

  // 先处理左子树
  if (node.left) {
    lastNodeInList = convertNode(node.left, lastNodeInList);
  }

  // 将当前节点与原双向链表拼接
  node.left = lastNodeInList;
  if (lastNodeInList) {
    lastNodeInList.right = node;
  }

  // 处理右子树
  lastNodeInList = node;
  if (node.right) {
    lastNodeInList = convertNode(node.right, lastNodeInList);
  }

  // 返回新链表的尾节点
  return lastNodeInList;
}

/**
 *
 * @param {TreeNode} root
 */
function convertTreeToList(root) {
  let lastNodeInList = convertNode(root);
  let headOfList = lastNodeInList;
  // 返回转化好的双向链表的头节点
  while (headOfList && headOfList.left) {
    headOfList = headOfList.left;
  }
  return headOfList;
}

/**
 * 测试代码
 */

const root = new TreeNode(
  10,
  new TreeNode(6, new TreeNode(4), new TreeNode(8)),
  new TreeNode(14, new TreeNode(12), new TreeNode(16))
);

let nodeOfList = convertTreeToList(root);
while (nodeOfList) {
  console.log(nodeOfList.value);
  nodeOfList = nodeOfList.right;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68