题目描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。

要求不能创建任何新的结点，只能调整树中结点指针的指向。

注意：

需要返回双向链表最左侧的节点。
例如，输入下图中左边的二叉搜索树，则输出右边的排序双向链表。

不同深度优先遍历

展开后的单链表应该与二叉树 中序遍历 顺序相同（算法1,2）
（算法3：展开后的单链表应该与二叉树 先序遍历 顺序相同）

算法1

(中序遍历)

时间复杂度

参考文献

class Solution {
public:
    TreeNode* prev  = NULL;
    void midTree(TreeNode* root)
    {   //转双链表：左指针指上一个，右指针指下一个
        if(root==NULL) return;
        //先遍历左子树
        midTree(root->left);
        //跳出将左指针指向上一个节点
        root->left = prev;
        //如果上一个节点不为NULL，将上一个节点的右指针指向当前节点
        if(prev) prev->right = root;
        prev = root;
        midTree(root->right);

    }

    TreeNode* convert(TreeNode* root) {
        midTree(root);
        //从初始root向前找到头元素（头元素的left==NULL时）
        //还有当root==NULL时停止while
        while(root && root->left) root = root->left;
        return root;


    }
};

算法2

(中序遍历,创建新节点)

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    TreeNode* convert(TreeNode* root) {

        //中序遍历，先处理左子树（创建新节点，上面的方法没有）
        if(root == NULL) return root;

        TreeNode* l = convert(root->left);
        if(l) //保证左子树不为空
        {
            //处理根节点的左指针，上一节点(左子树)的右指针
            TreeNode* cur = root->left;
            while(cur->right) cur= cur->right; 
            cur->right = root;
            root->left = cur;
        }
        else l = root;

        //保证root的右子树不为空
        if(root->right==NULL) return l;
        TreeNode* r= convert(root->right);
        root->right =r;
        r->left = root;


        return l;

    }
};

C++ 代码

算法3

(先序遍历)

时间复杂度

参考文献

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    //先序遍历，转双向链表
    void flatten(TreeNode* root) {
        if(root==nullptr ) return;   
        //递归处理，将左右子树拉平   
        flatten(root->left); 
        flatten(root->right);
        //暂存拉平后的左右子树
        TreeNode* l = root->left;
        TreeNode* r = root->right;
        //将root右指针指向左子树，右指针指向root
        //保证左子树不为空          
        if(l) 
        {
            root->right = l; 
            l->left = root;
        }
        //保证root的右子树不为空
        if(r==NULL) return;
        //if(r->val==5) cout<<root->val<<endl;
        TreeNode* cur = root;
        //将当前root的最右节点（即原左子树的最后节点）指向右子树
        //保证左子树不为空 ,不然当前root没有后续，自身为尾节点
        if(l) while(cur->right) cur=cur->right;

        cur->right = r;
        r->left = cur;
        //先序遍历，头节点不变，但左指针一点要注意指向空
        root->left = nullptr; 

    }
    TreeNode* convert(TreeNode* root) {
        //先序遍历，转双向链表
        flatten(root);
        return root;

    }
};