二叉搜索树与双向链表

题目

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

例子




解法:中序遍历

/**
 * @desc 二叉搜索树与双向链表
 * @param {Node} root
 * @return {Node}
 */
let treeToDoublyList = function (root) {
  if (!root) return root;
  let pre = null, head = null;
  let inOrder = (root) => {
    if (!root) return;
    inOrder(root.left);
    if (!pre) {
      head = new Node(root.val);
      pre = head;
    } else {
      let now = new Node(root.val);
      pre.right = now;
      now.left = pre;
      pre = now;
    }
    inOrder(root.right);
  };
  inOrder(root);
  head.left = pre;
  pre.right = head;
  return head;
};


评论(0)

评论