Ex36 二叉搜索树与双向链表

题目描述

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

“head” 表示指向链表中有最小元素的节点。特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

解题思路

树的中序遍历得到的结果就是一个排序后的结果。

一个左子树的节点的左子树即为链表的向前的节点，其根节点即为链表向后的节点。

一个右子树的节点的根节点即为链表的向前的节点，其向上的父节点就是链表向后的节点。

代码

class Solution
{
public:
  Node *
  treeToDoublyList (Node *root)
  {
    if (!root)
      return root;
    Node *last_node = nullptr;
    tree_to_doubly_list (root, &last_node);
    Node *head = last_node;
    while (head && head->left)
      head = head->left;
    Node *tail = head;
    while (tail->right)
      {
        tail = tail->right;
      }
    head->left = tail;
    tail->right = head;
    return head;
  }

private:
  void
  tree_to_doubly_list (Node *node, Node **last_node)
  {
    if (!node)
      return;
    Node *cur = node;
    if (cur->left)
      tree_to_doubly_list (cur->left, last_node);
    cur->left = *last_node;
    if (*last_node)
      (*last_node)->right = cur;
    *last_node = cur;
    if (cur->right)
      tree_to_doubly_list (cur->right, last_node);
  }
};

结果

执行结果：通过

执行用时：16 ms, 在所有 C++ 提交中击败了12.47%的用户

内存消耗：7.9 MB, 在所有 C++ 提交中击败了15.95%的用户

备注

LeetCode上的题是将二叉搜索树转为循环双向链表，而《剑指Offer》上的题是将二叉搜索树转为双向链表。注意二者区别。