lintcode 453 将二叉树拆成链表
2018-06-17 21:54:33来源:未知 阅读 ()
将二叉树拆成链表
将一棵二叉树按照前序遍历拆解成为一个假链表
。所谓的假链表是说,用二叉树的 right 指针,来表示链表中的 next 指针。
注意事项
不要忘记将左儿子标记为 null,否则你可能会得到空间溢出或是时间溢出。
1
\
1 2
/ \ \
2 5 => 3
/ \ \ \
3 4 6 4
\
5
\
6
不使用额外的空间耗费。
这道题目很有趣的一点就是拆成右斜树的假链表,并且这道题目是按照前序遍历拆解,并不是按照数据大小拆解。
所以很容易的一个递归。
有两点需要思考,从哪里开始?(前序遍历)怎么拆?(保存左右儿子)
/** * 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: a TreeNode, the root of the binary tree * @return: */ void flatten(TreeNode * root) { // write your code here if(root==NULL) return; TreeNode *l=root->left; TreeNode *r=root->right; flatten(root->left); flatten(root->right); if(root->left==NULL) return ; else { TreeNode *t=root->left; while(t->right) t=t->right; root->left=NULL; root->right=l; t->right=r; } return; } };
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 二叉搜索树_BST 2020-05-30
- 二叉树 2020-05-02
- 二叉排序树 2020-05-02
- 二叉堆(3)SkewHeap 2020-02-20
- 二叉堆(2)LeftistHeap 2020-02-19
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash