Leetcode—426. 将二叉搜索树转化为排序的双向链表【中等】Plus

2024/11/20 16:18:45 来源：https://blog.csdn.net/qq_44631615/article/details/140663542 浏览: 次关键词：Leetcode—426. 将二叉搜索树转化为排序的双向链表【中等】Plus

2024每日刷题（148）

Leetcode—426. 将二叉搜索树转化为排序的双向链表

在这里插入图片描述

实现代码

/*
// 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 == nullptr) {return (Node*)nullptr;}// 中序遍历stack<Node*> st;Node* first = nullptr;Node* pre = nullptr;while(root != nullptr || !st.empty()) {// 左子树全部入栈while(root != nullptr) {st.push(root);root = root->left;}root = st.top(), st.pop();if(first == nullptr) {first = root;}if(pre != nullptr) {pre->right = root;root->left = pre;}pre = root;root = root->right;}first->left = pre;pre->right = first;return first;}
};