专栏首页aCloudDeveloperLeetCode:114_Flatten Binary Tree to Linked List | 将一棵二叉树变成链表的形式 | Medium

LeetCode:114_Flatten Binary Tree to Linked List | 将一棵二叉树变成链表的形式 | Medium

要求:Given a binary tree, flatten it to a linked list in-place.将二叉树转化为平坦序列的树。比如:

结题思路:

该题有个提示,转化后的树的序列正好是二叉树前序遍历所得到的序列,所以,该题第一个思路就是利用前序遍历的方式来做。

第二个思路:我们可以利用递归的思路,先对根节点进行处理,将root的左子树放到右子树,在将左子树中的最右端节点“嫁接”到右子树,接着上面得到的子树。接下来在用同样的方法处理当前二叉树的下一个节点。看下面一个图,即可明了。

我实现的是第二种思路,代码如下:

 1 struct TreeNode {
 2     int            val;
 3     TreeNode*    left;
 4     TreeNode*    right;
 5     TreeNode(int x): val(x), left(NULL),right(NULL) {}
 6 };
 7 
 8 void flatten(TreeNode *root)
 9 {
10     if (NULL == root)
11         return;
12     //使用stack的非递归方法
13     TreeNode *left = root->left;
14     TreeNode *right = root->right;
15 
16     if (left) {
17         root->right = left;
18         root->left = NULL;
19 
20         TreeNode *pTemp = left;
21         while (pTemp->right)
22             pTemp = pTemp->right;
23         pTemp->right = right;
24 
25         flatten(root->right);
26     }
27 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode:104_Maximum Depth of Binary Tree | 二叉树的最大深度 | Easy

    要求:求二叉树的深度(二叉树的深度为最远叶子节点到根节点的距离,即根节点到最远叶子节点的距离) Given a binary tree, find its ma...

    CloudDeveloper
  • 算法导论第十九章 斐波那契堆

      《算法导论》第二版中在讨论斐波那契堆之前还讨论了二项堆,但是第三版中已经把这块的内容放到思考题中,究极原因我想大概是二项堆只是个引子,目的是为了引出斐波那契...

    CloudDeveloper
  • LeetCode:110_Balanced Binary Tree | 平衡二叉树 | Easy

    要求:判断一棵树是否是平衡二叉树 Given a binary tree, determine if it is height-balanced. For ...

    CloudDeveloper
  • LeetCode 623. 在二叉树中增加一行(BFS/DFS)

    给定一个二叉树,根节点为第1层,深度为 1。在其第 d 层追加一行值为 v 的节点。

    Michael阿明
  • LeetCode Invert Binary Tree题目分析

    Invert a binary tree. 4 / \ 2 7 / \ / \1 3 6 9 to4 / \ 7 2 / \ / \9 6 3 1 Tri...

    desperate633
  • Redhat6.8搭建ftp服务器并限制用户目录和访问ip

    #useradd -s /sbin/nologin -d /home/test -g test test

    loong576
  • 使用redis分布式锁高并发下QPS测试,单机一秒下1千个订单

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    天涯泪小武
  • SpringBoot学习手册-第一篇开篇(注解篇)

    一、SpringBoot是什么 springBoot框架。前段一个月时间我简单总结了一下在学习springcloud中遇到的一些知识点。从今天开始...

    程序源代码
  • 局域网内的NIS服务器器搭建管理

    NIS(网络信息服务),用来集中账号信息管理。类似LDAP一样的功能哦,一般可以作为LAN内的用户认证服务器吧! NIS服务器提供的数据: /etc/passw...

    BGBiao
  • 初学Java Web(1)——Web概述

    已经很久没有更新博客了,过年忙着吃喝玩乐,就怠惰了一小下下?幸好这学期新开的课程都比较有趣——Java Web和Android。至少对于我自己来说,既充满挑战...

    我没有三颗心脏

扫码关注云+社区

领取腾讯云代金券