《剑指offer》— JavaScript(26)二叉搜索树与双向链表

大前端 2017-03-09

二叉搜索树与双向链表

题目描述

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

思路

  1. 递归思想:把大问题转换为若干小问题;
  2. 由于JavaScript中并没有链表或者Tree这样的原生数据结构,都是通过对象模拟的,因此最终要返回的是指向双向链表首结点的指针;
  3. 将左子树构成双向链表,返回的是左子树的尾结点,将其连接到root的左边;
  4. 将右子树构成双向链表,将其追加到root结点之后,并返回尾结点;
  5. 向左遍历返回的链表至头结点处,即为所求双向链表的首结点。

实现代码

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function Convert(pRootOfTree) {
    if (!pRootOfTree) {
        return null;
    }
    var lastNode = null;
    lastNode = ConvertNode(pRootOfTree, lastNode);
    var head = lastNode;
    while (head && head.left) {
        head = head.left;
    }
    return head;
}

function ConvertNode(node, lastNode) {
    if (!node) {
        return;
    }
    if (node.left) {
        lastNode = ConvertNode(node.left, lastNode);
    }
    node.left = lastNode;
    if (lastNode) {
        lastNode.right = node;
    }
    lastNode = node;
    if (node.right) {
        lastNode = ConvertNode(node.right, lastNode);
    }
    return lastNode;
}

相关推荐