剑指offer:二叉搜索树与双向链表

题目描述

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

1.递归

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:

    TreeNode* leftLast=NULL;

    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if(pRootOfTree==NULL){
            return NULL;
        }

        TreeNode* left=Convert(pRootOfTree->left);

        if(left){
            leftLast->right=pRootOfTree;
            pRootOfTree->left=leftLast;

        }

        leftLast=pRootOfTree;

        TreeNode* right=Convert(pRootOfTree->right);

        if(right){
            right->left=pRootOfTree;
            pRootOfTree->right=right;
        }

        return left==NULL?pRootOfTree:left;
    }
};
添加笔记

2.利用非递归的中序遍历

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        stack<TreeNode*> stk;
        TreeNode* p=pRootOfTree;

        TreeNode* newRoot=NULL;
        TreeNode* pre=NULL;
        bool isFirst=true;

        while(p!=NULL || !stk.empty()){
            while(p!=NULL){
                stk.push(p);
                p=p->left;
            }

            if(!stk.empty()){
                p=stk.top();
                stk.pop();

                if(isFirst){
                    isFirst=false;
                    newRoot=p;
                    pre=p;
                }else{
                    pre->right=p;
                    p->left=pre;
                    pre=p;
                }

                p=p->right;

            }

        }

        return newRoot;
    }
};

用非递归可以更加的清晰