带你快速刷完67道剑指offer

如果你想在校招中顺利拿到更好的offer,阿秀建议你多看看前人的经验 ,比如准备简历实习上岸经历校招总结阿里、字节、腾讯、美团等一二线大厂真实面经也欢迎来一起参加秋招打卡活动 等;如果你是计算机小白,学习/转行/校招路上感到迷茫或者需要帮助,可以点此联系阿秀;免费分享阿秀个人学习计算机以来的收集到的好资源,点此白嫖;如果你需要《阿秀的学习笔记》网站中求职相关知识点的PDF版本的话,可以点此下载

# No26、二叉搜索树与双向链表

牛客网原题链接 (opens new window)

# 题目描述

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

# 0、最笨的一种写法,这也是最容易理解的一种方法了

中序遍历二叉树,然后用一个数组类保存遍历的结果,这样在数组中节点就按顺序保存了,然后再来修改指针,虽然没有一点技术含量,但是最后竟然还通过了 哈哈哈。。。

TreeNode* Convert(TreeNode* pRootOfTree)
{
	if (pRootOfTree == NULL) return pRootOfTree;
	vector<TreeNode*> result;
	Convert(pRootOfTree, result);
	return Convert(result);
}

void Convert(TreeNode* node,vector<TreeNode*>&result) {
	if (node->left != nullptr)
		Convert(node->left, result);
	result.push_back(node);
	if (node->right != nullptr)
		Convert(node->right, result);
}

TreeNode* Convert(vector<TreeNode*>& result) {
	for (int i = 0; i < result.size()-1; ++i) {
		result[i]->right = result[i + 1];
		result[i+1]->left = result[i];
}
	return result[0];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 0-1借助栈和数组类进行数据保存,最后修改指针指向

关键在于二叉树的层次遍历这一块

public:
   TreeNode* Convert(TreeNode* pRootOfTree)
{
	if (pRootOfTree == nullptr) return nullptr;
	vector<TreeNode*> result;
	stack<TreeNode*> s;

	// 形成一个中序遍历的结果,并添加指针。
	while (!s.empty() || pRootOfTree != nullptr) {
		if (pRootOfTree != nullptr) {
			s.push(pRootOfTree);
			pRootOfTree = pRootOfTree->left;
		}
		else {
			pRootOfTree = s.top();
			s.pop();
			result.push_back(pRootOfTree);
			pRootOfTree = pRootOfTree->right;
		}
	}
	// 修改链表指针指向。
	for (int i = 0; i < result.size() - 1; ++i) {
		result[i + 1]->left = result[i];
		result[i]->right = result[i+1];
	}
	return result[0];
}
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

# 1、借助栈进行节点保存,很厉害的一种写法

我服啦,采用的是跟剑指offer上一样的写法

  1. 明确Convert函数的功能。 输入:输入一个二叉搜索树的根节点。 过程:将其转化为一个有序的双向链表。 输出:返回该链表的头节点。
  2. 明确成员变量pLast的功能。 pLast用于记录当前链表的末尾节点。
  3. 明确递归过程。 递归的过程就相当于按照中序遍历,将整个树分解成了无数的小树,然后将他们分别转化成了一小段一小段的双向链表。再利用pLast记录总的链表的末尾,然后将这些小段链表一个接一个地加到末尾。
TreeNode* Convert(TreeNode* pRootOfTree)
{
    TreeNode* head = NULL, * pre = NULL;//head 输出,pre记录上一次出栈值
	stack<TreeNode*> s;
	while (pRootOfTree || !s.empty())
	{
		while (pRootOfTree!=nullptr)
		{
			s.push(pRootOfTree);
			pRootOfTree = pRootOfTree->left;
		}
		if (!s.empty())
		{
			pRootOfTree = s.top();
			s.pop();
			if (pre != NULL)
			{
				pre->right = pRootOfTree;
				pRootOfTree->left = pre;
			}
			else//pre为空,表示s第一次出栈,第一次出栈值为最左值,即输出值
			{
				head = pRootOfTree;
			}
			pre = pRootOfTree;
			pRootOfTree = pRootOfTree->right;
		}
	}
	return head;
}
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

# 2、复杂一点的递归做法

先将左子树变为有序的排序链表,再将右子树变为有序的链表,然后将当前结点插入在两个链表中间就可以了,需要注意左子树和右子树为空的情况

TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if(pRootOfTree == NULL)
            return NULL;
          
        TreeNode* leftTree = Convert(pRootOfTree->left);    // 将左子树变为排序链表
        TreeNode*   rightTree = Convert(pRootOfTree->right);   // 将右子树变为排序链表
        TreeNode* tmp = leftTree;
        if(tmp != NULL)
        {
            while(tmp->right)
            {
                tmp = tmp->right;
            }
            tmp->right     = pRootOfTree;
        }
         
        pRootOfTree->left  = tmp;
        pRootOfTree->right =  rightTree;
        if(rightTree != NULL)
            rightTree->left  = pRootOfTree;
          
        return(leftTree == NULL ? pRootOfTree:leftTree);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 3、简单递归做法,精简版

TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if(pRootOfTree == NULL) return pRootOfTree;
        pRootOfTree = ConvertNode(pRootOfTree);
        while(pRootOfTree->left) pRootOfTree = pRootOfTree->left;
        return pRootOfTree;
    }
 
    TreeNode* ConvertNode(TreeNode* root)
    {
        if(root == NULL) return root;
        if(root->left)
        {
            TreeNode *left = ConvertNode(root->left);
            while(left->right) left = left->right;
            left->right = root;
            root->left = left;
        }
         
        if(root->right)
        {
            TreeNode *right = ConvertNode(root->right);
            while(right->left) right = right->left;
            right->left = root;
            root->right = right;
        }
        return root;
    }
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

# 二刷:

# 1、借助stack和vector

运行时间:2ms 占用内存:408k

    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if(pRootOfTree == nullptr) return nullptr;
        stack<TreeNode*> st;
        vector<TreeNode*> result;
        while( !st.empty() || pRootOfTree != nullptr){
            if(pRootOfTree != nullptr){
                st.push(pRootOfTree);
                pRootOfTree = pRootOfTree->left;
                
            }
            else{
               pRootOfTree = st.top();
               st.pop();
               result.push_back(pRootOfTree);
                pRootOfTree = pRootOfTree->right;
            }
        }
        
        
       for(int i = 0; i < result.size()-1; ++i){
           
           result[i+1]->left = result[i];
           result[i]->right = result[i+1];
       }
        
        return result[0];
    }
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

# 2、依然是栈,不过节约了不少空间,记这种做法,很棒

运行时间:2ms 占用内存:484k

 TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if(pRootOfTree == nullptr) return nullptr;
        stack<TreeNode*> st;
        vector<TreeNode*> result;
        TreeNode* head = nullptr,*pre = nullptr;
        while( !st.empty() || pRootOfTree != nullptr){
            while(pRootOfTree != nullptr){
                st.push(pRootOfTree);
                pRootOfTree = pRootOfTree->left;
            }
            if( !st.empty()){
                pRootOfTree = st.top();
                st.pop();
              if(pre == nullptr){//表示第一次出栈,为最左值,记录下最小的元素
                  head = pRootOfTree;
              }
              else{
                  pre->right = pRootOfTree;
                  pRootOfTree->left = pre;
               }
                
                pre = pRootOfTree;
                pRootOfTree = pRootOfTree->right;
            }
        }
        return head;
    }
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