【经典题】二叉搜索树与双向链表

简介: 【经典题】二叉搜索树与双向链表

二叉搜索树与双向链表链接


解题思路


思路1 : 中序遍历,将节点放进vector中,再改链接关系,这很容易想出并解决,但这样明显不符合题意。



8017b1bb4bde4013aea1dfddb434a0f3.png



思路2:

这道题目要求将一个二叉搜索树转换成一个排序的双向链表,不创建新的节点,只调整指针。

二叉搜索树的特点是左子树的值都小于根节点,右子树的值都大于根节点,中序遍历可以得到一个升序的序列。

因此,我们可以利用中序遍历的顺序,将每个节点的左指针指向前一个节点,将每个节点的右指针指向后一个节点,从而形成一个双向链表。

我们需要用一个变量prev来记录前一个节点,初始为nullptr。然后我们递归遍历二叉树,每次访问到一个节点时,就修改它和prev的指针,并更新prev为当前节点。

最后,我们从根节点开始往左走,找到最左边的节点,即双向链表的头节点,返回即可。


37e209c67e6c40cbb6b4bc6e7602b521.png

举个栗子:

假设我们有这样一个二叉搜索树:

10
      /  \
    6    14
    / \   / \
   4   8 12 16



我们先初始化prev为空,然后从根节点开始递归遍历二叉树。


首先我们遍历到4这个节点,它没有左子树,所以我们直接修改它的左指针指向prev(此时为空),然后将prev更新为4。


然后我们回到6这个节点,它有左子树,所以我们修改它的左指针指向prev(此时为4),并将4的右指针指向6。然后将prev更新为6。


然后我们遍历到8这个节点,它没有左子树,所以我们修改它的左指针指向prev(此时为6),并将6的右指针指向8。然后将prev更新为8。


然后我们回到10这个节点,它有左子树,所以我们修改它的左指针指向prev(此时为8),并将8的右指针指向10。然后将prev更新为10。


然后我们遍历到12这个节点,它没有左子树,所以我们修改它的左指针指向prev(此时为10),并将10的右指针指向12。然后将prev更新为12。


然后我们回到14这个节点,它有左子树,所以我们修改它的左指针指向prev(此时为12),并将12的右指针指向14。然后将prev更新为14。


然后我们遍历到16这个节点,它没有左子树,所以我们修改它的左指针指向prev(此时为14),并将14的右指针指向16。然后将prev更新为16。


最后我们回到根节点10,并从它开始往左走,找到最左边的节点4,即双向链表的头节点。返回4即可。


此时二叉搜索树已经转换成了如下的双向链表:


850564badefa427fbc665ba5de8db8e4.png


代码—加注释

/*
struct TreeNode {
    int val; // 节点的值
    struct TreeNode *left; // 左子节点的指针
    struct TreeNode *right; // 右子节点的指针
    TreeNode(int x) : // 构造函数,初始化节点的值和子节点指针
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
  public:
    void InOrderConvert(TreeNode* cur, TreeNode*& prev) {
        if (cur == nullptr) // 如果当前节点为空,直接返回
            return;
        InOrderConvert(cur->left, prev); // 递归遍历左子树
        //这里cur出现的顺序就是中序
        cur->left = prev; // 将当前节点的左指针指向前一个节点
        if (prev) // 如果前一个节点不为空,将其右指针指向当前节点
            prev->right = cur;
        prev = cur; // 更新前一个节点为当前节点
        InOrderConvert(cur->right, prev); // 递归遍历右子树
    }
    TreeNode* Convert(TreeNode* pRootOfTree) {
        TreeNode* prev = nullptr; // 初始化前一个节点为空
        InOrderConvert(pRootOfTree,
                       prev); // 调用辅助函数,中序遍历二叉树,并修改指针
        TreeNode* head = pRootOfTree; // 初始化头节点为根节点
        while (head &&
                head->left) { // 循环找到最左边的节点,即双向链表的头节点
            head = head->left;
        }
        return head; // 返回头节点
    }
};


本节完

相关文章
剑指offer(C++)-JZ36:二叉搜索树与双向链表(数据结构-树)
剑指offer(C++)-JZ36:二叉搜索树与双向链表(数据结构-树)
|
存储
【LeetCode】236. 二叉树的最近公共祖先、 JZ36 二叉搜索树与双向链表
236. 二叉树的最近公共祖先 236. 二叉树的最近公共祖先 题目描述:
65 0
|
6月前
剑指 Offer 36:二叉搜索树与双向链表
剑指 Offer 36:二叉搜索树与双向链表
30 0
二叉树习题系列1--将二叉搜索树排序树转化为双向链表
二叉树习题系列1--将二叉搜索树排序树转化为双向链表
|
算法
HashMap 可不可以不使用链表,而直接使用红黑树或者二叉搜索树或者 AVL 等其他的数据结构?
HashMap 可不可以不使用链表,而直接使用红黑树或者二叉搜索树或者 AVL 等其他的数据结构?
65 0
图解LeetCode——剑指 Offer 36. 二叉搜索树与双向链表
图解LeetCode——剑指 Offer 36. 二叉搜索树与双向链表
163 1
剑指offer_二叉树---二叉搜索树与双向链表
剑指offer_二叉树---二叉搜索树与双向链表
59 0
剑指offer 37. 二叉搜索树与双向链表
剑指offer 37. 二叉搜索树与双向链表
62 0
二叉搜索树与双向链表(剑指offer 36)Java
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。
二叉搜索树与双向链表(剑指offer 36)Java
牛客——二叉搜索树与双向链表
牛客——二叉搜索树与双向链表
66 0
牛客——二叉搜索树与双向链表