二叉树转双向链表

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. 代码实现