政子的博客

技术|学习|随笔

CodingInterview-二叉搜索树与双向链表

使用中序遍历可以解决这个问题。所以，就可以分别用递归或迭代来解决。但它们的具体思路类似，都是使用一个 listEnd 变量来跟踪转换后链表的结尾，然后将中序遍历的元素挨个插入结尾，并将结尾后移。

下面是递归解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
private:
    TreeNode* listStart;
    TreeNode* listEnd;
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        listStart=NULL;listEnd=NULL;
        doConvert(pRootOfTree);
        return listStart;
    }
    void doConvert(TreeNode* pRoot){
        if(pRoot==NULL) return;
        doConvert(pRoot->left);
        if(listStart==NULL) {listStart=pRoot;}
        pRoot->left=listEnd;
        if(listEnd!=NULL) listEnd->right=pRoot;
        listEnd=pRoot;
        doConvert(pRoot->right);
    }
};

这里是循环解法：

PS：必须要注意判断最外层 while 循环退出的条件是 !s.empty() || pCurrent!=NULL ，如果错误地把 || 写成 && ，那么将会错的很离谱。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/*
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)
    {
        TreeNode* listStart=NULL;
        TreeNode* listEnd=NULL;
        stack<TreeNode*> s;
        TreeNode* pCurrent=pRootOfTree;
        while(!s.empty() || pCurrent!=NULL){
            while(pCurrent!=NULL){
                s.push(pCurrent);
                pCurrent=pCurrent->left;
            }
            if(!s.empty()){
                pCurrent=s.top();
                s.pop();
                if(listStart==NULL) listStart=pCurrent;
                pCurrent->left=listEnd;
                if(listEnd!=NULL) listEnd->right=pCurrent;
                listEnd=pCurrent;
                pCurrent=pCurrent->right;
            }
        }
        return listStart;
    }
};