lintcode378. 将二叉树转换成双链表

妖狐艹你老母 2023-07-04 06:18 32阅读 0赞

将一个二叉树按照中序遍历转换成双向链表。

样例
    样例 1：
    
    输入:
    	    4
    	   / \
    	  2   5
    	 / \
    	1   3		
    
    输出: 1<->2<->3<->4<->5
    样例 2：
    
    输入:
    	    3
    	   / \
    	  4   1
    
    输出:4<->3<->1

/**
      * 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==NULL) return NULL;
            DoublyListNode*head=new DoublyListNode(0);
            DoublyListNode*p=head;
            build(root,p);
            head->next->prev=NULL;
            return head->next;
        }
        void build(TreeNode*root,DoublyListNode*&head)
        {
        
            if(root==NULL) return;
            build(root->left,head);
            DoublyListNode*p=new DoublyListNode(root->val);
            p->prev=head;
            head->next=p;
            head=p;
            build(root->right,head);
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，32人围观）

还没有评论，来说两句吧...

相关阅读

相关将二叉搜索树原地转换成排序的双向链表

双向链表的每一个节点有next和pre两个指针，二叉树的每个节点则有right和left两个指针，其中next，right指针都指向的是比当前节点大的下一个节点，pre和lef

布满荆棘的人生/ 2023年07月14日 05:23/ 0 赞/ 61 阅读

相关 lintcode378. 将二叉树转换成双链表

将一个二叉树按照中序遍历转换成双向链表。样例样例 1：输入: 4 / \ 2 5

妖狐艹你老母/ 2023年07月04日 06:18/ 0 赞/ 33 阅读

相关 109. 有序链表转换二叉搜索树

题目来源 [109. 有序链表转换二叉搜索树][109.] 题目描述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdG

系统管理员/ 2023年02月20日 12:16/ 0 赞/ 48 阅读

相关经典面试题：将有序数组、有序链表转换成平衡二叉树

> 微信搜一搜：`bigsai` > [大家都在关注的刷题、学习数据结构和算法宝藏项目][Link 1] > 关注回复进群即可加入力扣打卡群，欢迎划水。将有序数组

r囧r小猫/ 2023年01月10日 10:22/ 0 赞/ 27 阅读

相关二叉树转换成双向链表

void convert(TreeNode\ root,TreeNode\\ preNode,TreeNode\\ head)\{ if (root==NULL) re

谁践踏了优雅/ 2022年08月09日 00:57/ 0 赞/ 173 阅读

相关二叉查找树转换成排序的双向链表

题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。比如将二元查找树 10 / \\ 6 14

左手的ㄟ右手/ 2022年08月08日 00:56/ 0 赞/ 182 阅读

相关【数据结构】二叉搜索树——转换成有序双向链表

在上一篇博客中，我们对二叉搜索树已经有了简单的认识。下面我们看看怎样将二叉搜索树转换成有序的双向链表在二叉搜索树中，左子树结点的值小于双亲结点的值，右子树结点的值大于双亲结

电玩女神/ 2022年06月01日 09:25/ 0 赞/ 240 阅读

相关将排序数组转换成平衡二叉树

![这里写图片描述][70] class TreeNode { int val; TreeNode left;

r囧r小猫/ 2022年05月19日 09:29/ 0 赞/ 179 阅读

相关将排序链表转换成二叉搜索树

![这里写图片描述][70] //链表的节点 class ListNode { int val; ListNode

川长思鸟来/ 2022年05月19日 07:45/ 0 赞/ 171 阅读

相关普通树转换成二叉树

如何将一棵树转化为对应的二叉树？解答： 1. 将节点的孩子放在左子树； 2. 将节点的兄弟放在右子树。例题： ![10895

╰半橙微兮°/ 2021年10月24日 04:22/ 0 赞/ 305 阅读