LeetCode(114): 二叉树展开为链表
2023-09-14 09:01:22 时间
Medium!
题目描述:
给定一个二叉树,原地将它展开为链表。
例如,给定二叉树
1 / \ 2 5 / \ \ 3 4 6
将其展开为:
1 \ 2 \ 3 \ 4 \ 5 \ 6
解题思路:
这道题要求把二叉树展开成链表,根据展开后形成的链表的顺序分析出是使用先序遍历,那么只要是数的遍历就有递归和非递归的两种方法来求解,这里我们也用两种方法来求解。
首先来看递归版本的,思路是先利用DFS的思路找到最左子节点,然后回到其父节点,把其父节点和右子节点断开,将原左子结点连上父节点的右子节点上,然后再把原右子节点连到新右子节点的右子节点上,然后再回到上一父节点做相同操作。
C++解法一:
1 // Recursion 2 class Solution { 3 public: 4 void flatten(TreeNode *root) { 5 if (!root) return; 6 if (root->left) flatten(root->left); 7 if (root->right) flatten(root->right); 8 TreeNode *tmp = root->right; 9 root->right = root->left; 10 root->left = NULL; 11 while (root->right) root = root->right; 12 root->right = tmp; 13 } 14 };
例如,对于下面的二叉树,上述算法的变换的过程如下:
1 / \ 2 5 / \ \ 3 4 6 1 / \ 2 5 \ \ 3 6 \ 4 1 \ 2 \ 3 \ 4 \ 5 \ 6
下面我们再来看非迭代版本的实现,这个方法是从根节点开始出发,先检测其左子结点是否存在,如存在则将根节点和其右子节点断开,将左子结点及其后面所有结构一起连到原右子节点的位置,把原右子节点连到原左子结点最后面的右子节点之后。
C++解法二:
1 // Non-recursion 2 class Solution { 3 public: 4 void flatten(TreeNode *root) { 5 TreeNode *cur = root; 6 while (cur) { 7 if (cur->left) { 8 TreeNode *p = cur->left; 9 while (p->right) p = p->right; 10 p->right = cur->right; 11 cur->right = cur->left; 12 cur->left = NULL; 13 } 14 cur = cur->right; 15 } 16 } 17 };
例如,对于下面的二叉树,上述算法的变换的过程如下:
1 / \ 2 5 / \ \ 3 4 6 1 \ 2 / \ 3 4 \ 5 \ 6 1 \ 2 \ 3 \ 4 \ 5 \ 6
前序迭代解法如下:
C++解法三:
1 class Solution { 2 public: 3 void flatten(TreeNode* root) { 4 if (!root) return; 5 stack<TreeNode*> s; 6 s.push(root); 7 while (!s.empty()) { 8 TreeNode *t = s.top(); s.pop(); 9 if (t->left) { 10 TreeNode *r = t->left; 11 while (r->right) r = r->right; 12 r->right = t->right; 13 t->right = t->left; 14 t->left = NULL; 15 } 16 if (t->right) s.push(t->right); 17 } 18 } 19 };
此题还可以延伸到用中序,后序,层序的遍历顺序来展开原二叉树,分别又有其对应的递归和非递归的方法,有兴趣的童鞋可以自行实现。
相关文章
- LeetCode周赛302,这也太卷了,20分钟ak也只有300名……
- LeetCode周赛290,什么?你不会树状数组,这太不公平了
- leetcode-124. 二叉树中的最大路径和(树形dp)
- LeetCode 905. 按奇偶排序数组
- LeetCode 2197. 替换数组中的非互质数(栈)
- leetcode二叉树的层次遍历_完全二叉树的中序序列
- JavaScript刷LeetCode拿offer-树的遍历
- LeetCode笔记:Biweekly Contest 89
- JavaScript刷LeetCode拿offer-二叉树层序遍历篇
- 前端工程师leetcode算法面试必备-二叉树深度广度遍历
- 前端工程师leetcode算法面试必备-二叉树的构造和遍历
- 刷完这19道leetcode二分查找算法,不信进不了大厂
- leetcode 1351. 统计有序矩阵中的负数 js实现
- leetcode刷题(127)——1575. 统计所有可行路径
- LeetCode - #64 最小路径和(Top 100)
- 前端工程师leetcode算法之二叉树的构造和遍历
- 前端工程师leetcode算法面试之简单的二叉树
- JavaScript刷LeetCode拿offer-二叉树层序遍历篇5
- LeetCode-102-二叉树的层序遍历
- LeetCode-416-分割等和子集
- Leetcode 111. 二叉树的最小深
- 前端工程师leetcode算法面试必备-二分搜索算法(下)_2023-03-15
- 每日一道leetcode:4. 寻找两个正序数组的中位数
- leetcode每日一题:数组的相对排序
- leetcode: 二叉树的层序遍历
- LeetCode——遍历序列构造二叉树
- LeetCode——根据二叉树创建字符串与二叉树的最近公共祖先
- LeetCode——二叉树的层序遍历