题目

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

需要返回双向链表最左侧的节点。

示例

• 示例1

二叉树
      10
    /    \
   6      14
 /  \     /  \
4    8   12   16

转换后的双向链表(LeetCode 里是双向循环链表)

4 <=> 6 <=> 8 <=> 10 <=> 12 <=> 14 <=> 16

代码

• DFS + 特判 视频讲解

class Solution {
public:
    TreeNode* convert(TreeNode* root) {
        if(!root) return NULL;
        auto sides = dfs(root);
        return sides.first;
    }

    pair<TreeNode*, TreeNode*> dfs(TreeNode* root){
        if(!root->left && !root->right) return {root,root};
        if(root->left && root->right){
            // 递归遍历左右子树
            auto lsides = dfs(root->left), rsides = dfs(root->right);
            lsides.second->right = root, root->left = lsides.second;
            root->right = rsides.first, rsides.first->left = root;
            // 返回两端节点
            return {lsides.first, rsides.second};
        }
        if(root->left){
            // 递归遍历左子树
            auto lsides = dfs(root->left);
            lsides.second->right = root, root->left = lsides.second;

            // 返回两端节点
            return {lsides.first, root};
        }
        if(root->right){
            // 递归遍历右子树
            auto rsides = dfs(root->right);
            root->right = rsides.first, rsides.first->left = root;
            // 返回两端节点
            return {root, rsides.second};
        }
    }
};

• DFS

// 二叉搜索树 中序遍历 递增
class Solution {
public:
    TreeNode *pre = NULL, *head = NULL;

    TreeNode* convert(TreeNode* root) {
        if (!root) return NULL;
        dfs(root);

        // leetcode 是 循环链表,  要加上 这里
        // 循环链表 首尾相连, pre 最后在 链表尾结点
        //head->left = pre, pre->right = head;

        return head;
    }

    void dfs(TreeNode* cur) { // 此处 用 cur 更贴切
        if (!cur) return;

        dfs(cur->left); // 中序遍历: 左中右

        if (!pre) head = cur; // pre为NULL, 找到头结点
        else { // 存在 pre, 将 pre 与 cur 左右 互连 
            pre->right = cur; 
            cur->left = pre;
        }

        pre = cur; // 更新 pre

        dfs(cur->right);
    }
};

两种方法都很强，俺受教了！先记下来慢慢看。

题目：二叉搜索树与双向链表