湖南城市建设网站,亚马逊雨林视频,波纹工作室 网站,郑州网约车资格证网上报名文章目录1. 题目2. 解题1. 题目
将一个 二叉搜索树 就地转化为一个 已排序的双向循环链表 。
对于双向循环列表#xff0c;你可以将左右孩子指针作为双向循环链表的前驱和后继指针#xff0c;第一个节点的前驱是最后一个节点#xff0c;最后一个节点的后继是第一个节点。 …
文章目录1. 题目2. 解题1. 题目
将一个 二叉搜索树 就地转化为一个 已排序的双向循环链表 。
对于双向循环列表你可以将左右孩子指针作为双向循环链表的前驱和后继指针第一个节点的前驱是最后一个节点最后一个节点的后继是第一个节点。
特别地我们希望可以 就地 完成转换操作。 当转化完成以后树中节点的左指针需要指向前驱树中节点的右指针需要指向后继。 还需要返回链表中最小元素的指针。
示例 1
示例 2
输入root [2,1,3]
输出[1,2,3]示例 3
输入root []
输出[]
解释输入是空树所以输出也是空链表。示例 4
输入root [1]
输出[1]提示
-1000 Node.val 1000
Node.left.val Node.val Node.right.val
Node.val 的所有值都是独一无二的
0 Number of Nodes 2000来源力扣LeetCode 链接https://leetcode-cn.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
采用二叉树的非递归遍历写法即可
/*
// 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* treeToDoublyList(Node* root) {if(!root)return root;stackNode* stk;Node *cur, *head NULL, *prev NULL;while(root || !stk.empty()){while(root){stk.push(root);root root-left;}cur stk.top();stk.pop();if(!head)head cur;//头结点root cur-right;cur-left prev;//当前节点的前驱if(prev)prev-right cur;//前面节点的后驱prev cur;//前节点更新}cur-right head;//最后的尾节点后继是头head-left cur;//头节点的前驱是尾节点return head;//返回头}
};12 ms 7.4 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
