剑指 Offer-36 二叉搜索树与双向链表c++

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了剑指 Offer-36 二叉搜索树与双向链表c++，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1381字，纯文字阅读大概需要2分钟。

内容图文

题目描述

解法 dfs

很容易发现这题就是考察二叉搜素树的中序遍历是递增序列的性质。
我们先写出中序遍历的代码

void dfs(Node* root) {
	if(root == NULL) return;
	dfs(root -> left);
	cout << root -> val;
	dfs(root -> right);
}

可以发现只要对中间的主体做出改动，使遍历过程中的结点指针指向对应位置就能形成双向链表。
但题目还要求是循环链表，所以我们需要记录头结点和尾结点的位置。
思路：
连接部分：设置pre结点，初始值为空，dfs函数的参数为cur结点。递归过程中

		pre -> right = cur;
        cur -> left = pre;
        pre = cur;

头尾结点部分：
设置局部变量head，调用dfs初次进入递归的中间部分时，说明我们到了头结点，于是head = cur。

		if(pre == NULL) head = cur; 
		else pre -> right = cur;
	    cur -> left = pre;
        pre = cur;

作为递归函数的上一个结点，当cur为空时（即递归结束时），pre就是尾结点。

 		dfs(root);
		pre -> right = head;
 		head -> left = pre;

于是得到完整代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
public:
        Node* pre;
        Node* head;
    Node* treeToDoublyList(Node* root) {
        if(root == NULL) return nullptr;
        pre = NULL;
        dfs(root);
        pre -> right = head;
        head -> left = pre;
        return head;
    }
    void dfs(Node* cur) {
        if(cur == NULL) return;
        dfs(cur -> left);
        if(pre == NULL) head = cur; 
        else pre -> right = cur;
        cur -> left = pre;
        pre = cur;
        dfs(cur -> right);
    }
};

内容总结

以上是互联网集市为您收集整理的剑指 Offer-36 二叉搜索树与双向链表c++全部内容，希望文章能够帮你解决剑指 Offer-36 二叉搜索树与双向链表c++所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端