首页 > 代码库 > 算法题——二叉树转换为左单链表
算法题——二叉树转换为左单链表
题目：给定一棵二叉树，将所有的结点都放到左儿子的位置，即除了root结点外，每一个结点都是其他某一个结点的左儿子。不用保持某种顺序，不能递归，O(1)空间。
思路：
我的想法是，维持一个遍历指针p，另一个指针tail永远指向向左遍历到底的结点；
初始化p和tail都为root，开始循环：
- 如果p为叶子结点，则退出循环；
- 如果p没有右儿子，则向左下降一层；
- 如果p有右儿子，则tail向左遍历到底，将p的右子树挂到tail的左儿子上，p右儿子赋空值，然后向左下降一层。
p每次下降一层时，tail从上一个底层结点向左遍历到新底层结点，遍历的结点树为树高O(lg N)；p共下降了N层，时间复杂度为O(N * lgN)。
代码：
1 TreeNode *btree2LeftList(TreeNode *root) 2 { 3 if(root == NULL) 4 return root; 5 6 TreeNode *p = root, *tail = root; //p遍历，tail向左遍历到底 7 8 while(p->left != NULL || p->right != NULL) //p为叶子时退出循环 9 {10 if(p->right != NULL)11 {12 while(tail->left != NULL) //p有右子树，则tail向左遍历到底，将p的右子树挂到tail左儿子13 {14 tail = tail->left;15 }16 tail->left = p->right;17 p->right = NULL;18 }19 p = p->left;20 }21 22 return root;23 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。