文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

將一個二叉樹按照中序遍歷轉(zhuǎn)換成雙向鏈表。

樣例

樣例 1： 輸入:4/ \2 5/ \1 3 輸出: 1<->2<->3<->4<->5樣例 2： 輸入:3/ \4 1輸出:4<->3<->1

https://www.lintcode.com/problem/convert-binary-tree-to-doubly-linked-list/description

2. 解題

• 非遞歸中序遍歷，使用棧

/*** Definition of Doubly-ListNode* class DoublyListNode {* public:* int val;* DoublyListNode *next, *prev;* DoublyListNode(int val) {* this->val = val;* this->prev = this->next = NULL;* }* } * Definition of TreeNode:* class TreeNode {* public:* int val;* TreeNode *left, *right;* TreeNode(int val) {* this->val = val;* this->left = this->right = NULL;* }* }*/class Solution { public:/*** @param root: The root of tree* @return: the head of doubly list node*/DoublyListNode * bstToDoublyList(TreeNode * root) {// write your code hereif(!root) return NULL;stack<TreeNode*> stk;DoublyListNode *h = new DoublyListNode(-1), *pre = h;while(!stk.empty() || root){while(root){stk.push(root);root = root->left;}root = stk.top();stk.pop();DoublyListNode *cur = new DoublyListNode(root->val);pre->next = cur;cur->prev = pre;pre = cur;root = root->right;}DoublyListNode *head = h->next;h->next = NULL;head->prev = NULL;delete h;return head;} };

50 ms C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關(guān)注我的公眾號（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LintCode 378. 将二叉树转换成双链表（非递归遍历）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。