剑指offer-26. 二叉搜索树与双向链表

题目描述

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

解题思路：

【中序遍历】

    1.递归左子树。

    2.如果当前结点不为空的话，将当前pRootOfTree追加到链表。

    3.递归右子树。

    4.重复上述过程直到遍历完整棵树。

代码实现：

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
    /*
    解题思路：
    【中序遍历】
    1.递归左子树。
    2.如果当前结点不为空的话，将当前pRootOfTree追加到链表。
    3.递归右子树。
    4.重复上述过程直到遍历完整棵树。
    */
public:
    TreeNode* current = NULL;
    TreeNode* head = NULL;
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        ConvertFun(pRootOfTree);
        return head;
    }
    void ConvertFun(TreeNode* pRootOfTree){
        if(pRootOfTree == NULL){
            return;
        }
        ConvertFun(pRootOfTree->left);
        if(current == NULL){
            current = pRootOfTree;
            head = pRootOfTree;
        }else{
            current->right = pRootOfTree;
            pRootOfTree->left = current;
            current = pRootOfTree;
        }
         ConvertFun(pRootOfTree->right);
    }
};
           

 效率：