[LeetCode] Flatten Binary Tree to Linked List
2023-09-11 14:17:25 时间
1 迭代,重要关系
p->right = s.top();
1 class flat{ 2 public: 3 void flatten(TreeNode* root) { 4 if (root == NULL) return; 5 stack<TreeNode*> s; 6 s.push(root); 7 while (!s.empty()) { 8 TreeNode *p = s.top(); 9 s.pop(); 10 if (p->right) 11 s.push(p->right); 12 if (p->left) 13 s.push(p->left); 14 p->left = NULL; 15 if (!s.empty()) 16 p->right = s.top(); 17 } 18 } 19 };
2 递归
思路:
1 搞定左边
2 搞定右边
3 将左边的插入到root 和right中间
3.1 找到左边的最后一个节点 left_most
3.2 left_most->right = root->right;
3.3 root->right = left
1 class flat{ 2 public: 3 void flatten_rec(TreeNode* root) { 4 if (root == NULL) return; 5 if(root->left == NULL && root->right == NULL) 6 return ; 7 8 flatten_rec(root->left); 9 flatten_rec(root->right); 10 11 TreeNode * left_most = root->left; 12 while(left_most && left_most->right) 13 { 14 left_most = left_most->right; 15 } 16 if(root->left != NULL) 17 { 18 left_most->right = root->right; 19 root->right = root->left; 20 } 21 22 root->left = NULL; 23 return ; 24 25 } 26 };
相关文章
- Leetcode 之Convert Sorted List to Binary Search Tree(55)
- leetcode 之Reverse Linked List II(15)
- Java实现 LeetCode 433 最小基因变化
- Java实现 LeetCode 392 判断子序列
- Java实现 LeetCode 374 猜数字大小
- Java实现 LeetCode 209 长度最小的子数组
- Java实现 LeetCode 57 插入区间
- Java实现 LeetCode 12 整数转罗马数字
- Java实现LeetCode #986 - Interval List Intersections
- Java实现LeetCode #986 - Interval List Intersections
- Java实现 LeetCode 240 搜索二维矩阵 II
- (LeetCode 141/142)Linked List Cycle
- LeetCode(64):最小路径和
- LeetCode(55): 跳跃游戏
- LeetCode:114_Flatten Binary Tree to Linked List | 将一棵二叉树变成链表的形式 | Medium
- (LeetCode 82)Remove Duplicates from Sorted List II
- [LeetCode] Remove Linked List Elements
- [LeetCode] Insertion Sort List
- LeetCode(119):杨辉三角 II
- LeetCode-1790. 仅执行一次字符串交换能否使两个字符串相等【字符串】
- Python 刷Leetcode题库,顺带学英语单词(1)
- LeetCode - 46 全排列
- leetcode 刷题之路 66 Path Sum II
- leetCode 82.Remove Duplicates from Sorted List II (删除排序链表的反复II) 解题思路和方法
- Leetcode 1207. 独一无二的出现次数
- 【LeetCode】Partition List
- LeetCode——Count and Say
- [LeetCode] Flatten Binary Tree to Linked List
- leetcode - Reverse Linked List II