网站服务器哪个好,濮阳网络科技有限公司,网站管理员登陆域名,品牌网站设计制作服务公司LeetCode 热题 100_二叉树展开为链表#xff08;46_114#xff09; 题目描述#xff1a;输入输出样例#xff1a;题解#xff1a;解题思路#xff1a;思路一#xff08;先序遍历#xff08;递归数组#xff09;#xff09;#xff1a;思路二#xff08;先序遍历46_114 题目描述输入输出样例题解解题思路思路一先序遍历递归数组思路二先序遍历非递归 代码实现代码实现思路一先序遍历递归数组代码实现思路二先序遍历非递归以思路一为例进行调试 题目描述
给你二叉树的根结点 root 请你将它展开为一个单链表
展开后的单链表应该同样使用 TreeNode 其中 right 子指针指向链表中下一个结点而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。
输入输出样例
示例 1
输入root [1,2,5,3,4,null,6] 输出[1,null,2,null,3,null,4,null,5,null,6]
示例 2 输入root [] 输出[]
示例 3 输入root [0] 输出[0]
提示 树中结点数在范围 [0, 2000] 内 -100 Node.val 100
题解
解题思路
思路一先序遍历递归数组
1、在进行先序遍历的时候先将结点的信息存储到数组中通过数组中的先后顺序更新每个结点的指向。
2、复杂度分析 ① 时间复杂度O(n)n为二叉树中节点的个数需遍历一遍二叉树O(n)遍历一遍数组更改指针的指向O(n)。 ② 空间复杂度O(n)递归遍历所需空间最多为O(n)一个额外的数组存储二叉树的信息On。
思路二先序遍历非递归
1、如果我们采用非递归的方式当我们遍历到一个结点时我们就可以用一个指针来记录先序遍历中上一个结点的信息通过修改上一个结点的指向来转换成单链表。
3、复杂度分析 ① 时间复杂度O(n)n为二叉树中节点的个数需遍历一遍二叉树O(n)。 ② 空间复杂度O(n)先序遍历的非递归实现需要借助栈实现最坏情况下栈中有n个结点信息。
代码实现
代码实现思路一先序遍历递归数组
//方法一递归采用递归的前序遍历将遍历的结点存储在数组中然后修改指针的指向
void flatten1(TreeNode* root) {//nums_TreeNode存放先序遍历各节点的顺序vectorTreeNode *nums_TreeNode;//先序遍历将结点信息存储在nums_TreeNode中preorder(root,nums_TreeNode);//根据nums_TreeNode中结点的顺序更改结点的指向for (int i 1; i nums_TreeNode.size(); i){nums_TreeNode[i-1]-leftnullptr;nums_TreeNode[i-1]-rightnums_TreeNode[i];}
}//先序遍历将结点信息存储在nums_TreeNode中
//注意vectorTreeNode *nums_TreeNode这里的引用
void preorder(TreeNode *root,vectorTreeNode *nums_TreeNode){if(rootnullptr) return;nums_TreeNode.emplace_back(root);preorder(root-left,nums_TreeNode);preorder(root-right,nums_TreeNode);
}代码实现思路二先序遍历非递归
//方法二非递归先序遍历,pre代表当前遍历结点的前一个结点改变pre左右孩子结点的指向
void flatten2(TreeNode* root) {if(rootnullptr) return ;stackTreeNode *stk;stk.push(root);//存放展开单链表的末尾TreeNode *tailnullptr;while (!stk.empty()){TreeNode *nodestk.top();stk.pop();//更改结点的指向if(tail!nullptr) {tail-leftnullptr;tail-rightnode;}//注意右子结点先入栈if(node-right!nullptr) stk.push(node-right);if(node-left!nullptr) stk.push(node-left);//更新单链表的尾结点tailnode;}
}以思路一为例进行调试
#includeiostream
#includevector
#includequeue
#includestack
using namespace std;struct TreeNode
{int val;TreeNode *left;TreeNode *right;TreeNode():val(0),left(nullptr),right(nullptr){}TreeNode(int val):val(val),left(nullptr),right(nullptr){}TreeNode(int val,TreeNode *left,TreeNode *right):val(val),left(left),right(right){}
};//通过数组创建二叉树数组中-1代表nullptr
TreeNode *createTree(vector int nums){if (nums.empty()) return nullptr;TreeNode *rootnew TreeNode(nums[0]);queueTreeNode * q;q.push(root);int i1;while (inums.size()){//注意这里不能用root,会改变root的指向TreeNode *nodeq.front();q.pop();if(inums.size()nums[i]!-1){node-leftnew TreeNode(nums[i]);q.push(node-left);}i;if(inums.size()nums[i]!-1){node-rightnew TreeNode(nums[i]);q.push(node-right);}i;}return root;
}//中序遍历输出二叉树用于验证二叉树是否创建正确
void inorder_Traversal(TreeNode *root){if(rootnullptr) return; inorder_Traversal(root-left);coutroot-val ;inorder_Traversal(root-right);
}class Solution
{
public://方法一递归采用递归的前序遍历将遍历的结点存储在数组中然后修改指针的指向void flatten1(TreeNode* root) {vectorTreeNode *nums_TreeNode;preorder(root,nums_TreeNode);for (int i 1; i nums_TreeNode.size(); i){nums_TreeNode[i-1]-leftnullptr;nums_TreeNode[i-1]-rightnums_TreeNode[i];}}//注意vectorTreeNode *nums_TreeNode这里的引用void preorder(TreeNode *root,vectorTreeNode *nums_TreeNode){if(rootnullptr) return;nums_TreeNode.emplace_back(root);preorder(root-left,nums_TreeNode);preorder(root-right,nums_TreeNode);}
};int main(){vectorint nums{1,2,5,3,4,-1,6};//通过数组创建二叉树-1为nullptrTreeNode* rootcreateTree(nums);//测试二叉树是否创建正确//inorder_Traversal(root);//二叉树展开为链表Solution s;s.flatten2(root);//输出转换的单链表while (root!nullptr){coutroot-val-;rootroot-right;}coutnullptr;return 0;
}
LeetCode 热题 100_二叉树展开为链表46_114)原题链接 欢迎大家和我沟通交流(✿◠‿◠)
