福州网站建设哪里有,网站建设方案,岳阳市住房和城乡建设路网站,小说网站防盗做的好处1. 题目
二叉树数据结构TreeNode可用来表示单向链表#xff08;其中left置空#xff0c;right为下一个链表节点#xff09;。 实现一个方法#xff0c;把二叉搜索树转换为单向链表#xff0c;要求值的顺序保持不变#xff0c;转换操作应是原址的#xff0c;也就是在原始…1. 题目
二叉树数据结构TreeNode可用来表示单向链表其中left置空right为下一个链表节点。 实现一个方法把二叉搜索树转换为单向链表要求值的顺序保持不变转换操作应是原址的也就是在原始的二叉搜索树上直接修改。
返回转换后的单向链表的头节点。
示例
输入 [4,2,5,1,3,null,6,0]
输出 [0,null,1,null,2,null,3,null,4,null,5,null,6]提示
节点数量不会超过 100000。来源力扣LeetCode 链接https://leetcode-cn.com/problems/binode-lcci 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
循环中序遍历
class Solution {
public:TreeNode* convertBiNode(TreeNode* root) {stackTreeNode* stk;TreeNode *prev NULL, *tp, *head NULL;while(root || !stk.empty()){while(root){stk.push(root);root root-left;}tp stk.top();stk.pop();tp-left NULL;if(prev)prev-right tp;if(!head)head tp;prev tp;root tp-right;}return head;}
};递归解法
class Solution {TreeNode* prev NULL;TreeNode* head NULL;
public:TreeNode* convertBiNode(TreeNode* root) {if(!root)return NULL;convertBiNode(root-left);if(prev)prev-right root;prev root;root-left NULL;if(!head){head root;prev root;}convertBiNode(root-right);return head;}
};
