• 二叉搜索树与双向链表
    • 题目
    • 解题思路

    二叉搜索树与双向链表

    题目

    牛客网

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

    解题思路

    1. 由于 BST 的特性，采用中序遍历正好符合排序
    2. 要考虑 root 节点要与 左节点的最大值连接，与右节点的最小值连接
    3. 增加一个已排序链表的指针，指向最后一个已排序节点
    1. public TreeNode Convert(TreeNode pRootOfTree) {
    2.     if (pRootOfTree == null) {
    3.         return null;
    4.     }
    6.     TreeNode[] nodeList = {new TreeNode(-1)};
    8.     ConvertToLink(pRootOfTree, nodeList);
    10.     TreeNode cursor = pRootOfTree;
    11.     while (cursor.left != null) {
    12.         cursor = cursor.left;
    13.     }
    15.     cursor.right.left = null;
    16.     return cursor.right;
    17. }
    19. private void ConvertToLink(TreeNode root, TreeNode[] nodeList) {
    20.     if (root == null) {
    21.         return;
    22.     }
    24.     ConvertToLink(root.left, nodeList);
    26.     root.left = nodeList[0];
    27.     nodeList[0].right = root;
    28.     nodeList[0] = root;
    30.     ConvertToLink(root.right, nodeList);
    31. }