金融网站建设方案,商昊网站建设,直播网站开发多少钱,在线网页爬虫工具2023每日刷题#xff08;九十八#xff09;
Leetcode—114. 二叉树展开为链表 Morris-like算法思想
可以发现展开的顺序其实就是二叉树的先序遍历。算法和 94 题中序遍历的 Morris 算法有些神似#xff0c;我们需要两步完成这道题。
将左子树插入到右子树的地方将原来的右…2023每日刷题九十八
Leetcode—114. 二叉树展开为链表 Morris-like算法思想
可以发现展开的顺序其实就是二叉树的先序遍历。算法和 94 题中序遍历的 Morris 算法有些神似我们需要两步完成这道题。
将左子树插入到右子树的地方将原来的右子树接到左子树的最右边节点考虑新的右子树的根节点一直重复上边的过程直到新的右子树为 null 实现代码
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:void flatten(TreeNode* root) {while(root ! nullptr) {if(root-left nullptr) {root root-right;} else {TreeNode* pre root-left;// pre指向root左子树最右结点while(pre-right ! nullptr) {pre pre-right;}pre-right root-right;root-right root-left;root-left nullptr;root root-right;}}}
};运行结果 前序遍历dfs算法思想
将二叉树展开为单链表之后单链表中的节点顺序即为二叉树的前序遍历访问各节点的顺序。因此可以对二叉树进行前序遍历获得各节点被访问到的顺序。由于将二叉树展开为链表之后会破坏二叉树的结构因此在前序遍历结束之后更新每个节点的左右子节点的信息将二叉树展开为单链表。
实现代码
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:void flatten(TreeNode* root) {vectorTreeNode* ans;// 前序遍历用ans记录顺序functionvoid(TreeNode*) dfs [](TreeNode* root) {if(root nullptr) {return;}ans.push_back(root);dfs(root-left);dfs(root-right);};dfs(root);int n ans.size();for(int i 1; i n; i) {TreeNode* pre ans.at(i - 1);TreeNode* cur ans.at(i);pre-left nullptr;pre-right cur;}}
};运行结果 之后我会持续更新如果喜欢我的文章请记得一键三连哦点赞关注收藏你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 ↖(▔▽▔)↗感谢支持
