题目描述
给定一个二叉树,原地将它展开为一个单链表。
示例:
例如,给定二叉树 1 / 2 5 / \ 3 4 6将其展开为:1 2 3 4 5 6
题目链接:https://leetcode-/problems/flatten-binary-tree-to-linked-list/
思路1
从例子中可以看到,链表的链接顺序是树的先序遍历的顺序。所以,先先序遍历树,并将序列存到队列中,然后将节点出队列,更改节点的左指针为空,右指针为下一个节点即可。代码如下:
/** * 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) { if(root==nullptr) return; queue<TreeNode*> q; dfs(root, q); TreeNode* head = q.front(); q.pop(); TreeNode* cur = head; while(!q.empty()){ TreeNode* node = q.front(); q.pop(); cur->left = nullptr; cur->right = node; cur = node; } } void dfs(TreeNode* root, queue<TreeNode*>& q){ if(root==nullptr) return; q.push(root); dfs(root->left, q); dfs(root->right, q); }};时间复杂度:O(n)
空间复杂度:O(n)
思路2
使用先序遍历(中左右)的反序(右左中)遍历,然后再串联起来。
代码如下:
/** * 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) { if(root==nullptr) return; doFlatten(root); } TreeNode* pre= nullptr; void doFlatten(TreeNode* root){ if(root==nullptr) return; doFlatten(root->right); doFlatten(root->left); root->left = nullptr; root->right = pre; pre = root; }};时间复杂度:O(n)
空间复杂度:O(h)
参考
https://leetcode-/problems/flatten-binary-tree-to-linked-list/solution/dong-hua-yan-shi-si-chong-jie-fa-114-er-cha-shu-zh/
来源:/content-4-719051.html
如果觉得《【LeetCode-链表】二叉树展开为链表》对你有帮助,请点赞、收藏,并留下你的观点哦!