深圳网站搜索,怎么做网页超链接,高校信息化建设 网站,软件项目管理课程二叉树展开为链表 理解题意#xff1a;前序遍历的N种写法题解1 前序遍历题解2 反前序遍历(代码简洁)题解3 类似旋转的方法题解4 迭代题解5 同时遍历改左右子树 给你二叉树的根结点
root #xff0c;请你将它展开为一个单链表#xff1a; 展开后的单链表应该同样使用 TreeNo… 二叉树展开为链表 理解题意前序遍历的N种写法题解1 前序遍历题解2 反前序遍历(代码简洁)题解3 类似旋转的方法题解4 迭代题解5 同时遍历改左右子树 给你二叉树的根结点
root 请你将它展开为一个单链表 展开后的单链表应该同样使用 TreeNode 其中 right 子指针指向链表中下一个结点而左子指针始终为 null 。 展开后的单链表应该与二叉树先序遍历顺序相同。 提示
树中结点数在范围 [0, 2000] 内-100 Node.val 100
理解题意前序遍历的N种写法
题解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 {vectorTreeNode* arr;
public:void dfs(TreeNode* root){if(! root) return;arr.push_back(root);dfs(root-left);dfs(root-right);} void flatten(TreeNode* root) {if(! root) return;dfs(root);for(int i 1; i arr.size(); i){root-right arr[i];root-left nullptr;root root-right;}}
};题解2 反前序遍历(代码简洁)
class Solution {TreeNode* preNode;
public:void flatten(TreeNode* root) {if (! root) return;// right先压栈后面弹flatten(root-right);flatten(root-left);// 第一次执行 root是前序遍历的最后访问的结点root-left NULL;root-right preNode;preNode root;}
};题解3 类似旋转的方法
class Solution {TreeNode* preNode;
public:void flatten(TreeNode* root) {TreeNode *curr root;while (curr ! nullptr) {if (curr-left ! nullptr) {auto next curr-left;auto predecessor next;while (predecessor-right ! nullptr) {predecessor predecessor-right;}predecessor-right curr-right;curr-left nullptr;curr-right next;}curr curr-right;}}
};题解4 迭代
class Solution {TreeNode* preNode;
public:void flatten(TreeNode* root) {auto v vectorTreeNode*();auto stk stackTreeNode*();TreeNode *node root;while (node ! nullptr || !stk.empty()) {while (node ! nullptr) {// 前序遍历 动作放在最前面v.push_back(node);stk.push(node);node node-left;}node stk.top(); stk.pop();node node-right;}int size v.size();for (int i 1; i size; i) {auto prev v.at(i - 1), curr v.at(i);prev-left nullptr;prev-right curr;}}
};题解5 同时遍历改左右子树
void flatten(TreeNode* root) {if (root nullptr) {return;}auto stk stackTreeNode*();stk.push(root);TreeNode *prev nullptr;while (!stk.empty()) {TreeNode *curr stk.top(); stk.pop();if (prev ! nullptr) {prev-left nullptr;prev-right curr;}TreeNode *left curr-left, *right curr-right;// 防止脏数据原数据先放进stack里if (right ! nullptr) {stk.push(right);}if (left ! nullptr) {stk.push(left);}//迭代prev curr;}}
