将一个二叉树按照中序遍历转换成双向链表。
样例
样例 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
/**
* 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 here
if(!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++