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

柔情只为你懂 2024-04-17 05:57 60阅读 0赞

# [剑指offer题型分类及各题的代码及解题思路][offer] #

## 1、题目描述 ##

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

### 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){}
    };

## 3、C++实现代码 ##

### **方法一：非递归版** ###

**`解题思路：`**

`1``.核心是中序遍历的非递归算法。`

`2``.修改当前遍历节点与前一遍历节点的指针指向。`

class Solution {
    public:
        TreeNode* Convert(TreeNode* pRootOfTree)
        {
            //二叉树为空，直接返回NULL
            if(pRootOfTree == NULL)
                return NULL;
            
            stack<TreeNode*> s;
            TreeNode* p = pRootOfTree;
            TreeNode* pre;
            TreeNode* head;
            bool isFirst = true;
            while(p != NULL || !s.empty())
            {
                //找到左子树的最左边的结点，即值最小的结点
                while(p != NULL)
                {
                    s.push(p);
                    p = p->left;
                }
                //p指向栈顶指针，其为即将连接的结点
                p = s.top();
                s.pop();
                //找到链表的头结点
                if(isFirst)
                {
                    head = p;
                    pre = head;
                    isFirst = false;
                }
                else
                {//从最小的结点开始，按顺序将结点连接起来
                    pre->right = p;
                    p->left = pre;
                    pre = p;
                }
                p = p->right;
            }
            return head;
        }
    };

### 方法二：递归版 ###

**`解题思路：`**

`1``.将左子树构造成双链表，并返回链表头节点。`

`2``.定位至左子树双链表最后一个节点。`

`3``.如果左子树链表不为空的话，将当前root追加到左子树链表。`

`4``.将右子树构造成双链表，并返回链表头节点。`

`5``.如果右子树链表不为空的话，将该链表追加到root节点之后。`

`6``.根据左子树链表是否为空确定返回的节点。`

class Solution {
    public:
        TreeNode* Convert(TreeNode* pRootOfTree)
        {
             if(pRootOfTree == NULL)
                return NULL;
            if(pRootOfTree->left == NULL && pRootOfTree->right == NULL)
                return pRootOfTree;
            // 1.将左子树构造成双链表，并返回链表头节点
            TreeNode* left = Convert(pRootOfTree->left);
            TreeNode* p = left;
            // 2.定位至左子树双链表最后一个节点
            while(p != NULL && p->right != NULL)
            {
                p = p->right;
            }
            // 3.如果左子树链表不为空的话，将当前root追加到左子树链表
            if(left != NULL)
            {
                p->right = pRootOfTree;
                pRootOfTree->left = p;
            }
            // 4.将右子树构造成双链表，并返回链表头节点
            TreeNode* right = Convert(pRootOfTree->right);
            // 5.如果右子树链表不为空的话，将该链表追加到root节点之后
            if(right != NULL)
            {
                right->left = pRootOfTree;
                pRootOfTree->right = right;
            }
            return left != NULL ? left : pRootOfTree;
        }
    };

[offer]: https://blog.csdn.net/qq_26079093/article/details/96605538