邢台手机网站建设信息,超链接html代码,wordpress 存储视频,网站空间租赁文章目录1. 题目2. 解题1. 题目
将一个二叉树按照中序遍历转换成双向链表。
样例
样例 1#xff1a;
输入:4/ \2 5/ \1 3 输出: 1-2-3-4-5样例 2#xff1a;
输入:3/ \4 1输出:4-3-1https://www.lintcode.com/pro…
文章目录1. 题目2. 解题1. 题目
将一个二叉树按照中序遍历转换成双向链表。
样例
样例 1
输入:4/ \2 5/ \1 3 输出: 1-2-3-4-5样例 2
输入:3/ \4 1输出:4-3-1https://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;stackTreeNode* 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/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
