LeetCode C++ 897. Increasing Order Search Tree【Tree/DFS】简单
发布日期:2021-07-01 02:53:02
浏览次数:2
分类:技术文章
本文共 2661 字,大约阅读时间需要 8 分钟。
Given a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only 1 right child.
Example 1:
Input: [5,3,6,2,4,null,8,1,null,null,null,7,9] 5 / \ 3 6 / \ \ 2 4 8 / / \ 1 7 9Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9] 1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ 8 \ 9
Constraints:
- The number of nodes in the given tree will be between
1
and100
. - Each node will have a unique integer value from
0
to1000
.
题意:给你一个树,按中序遍历重新排列树,使树中最左边的结点现在是树的根,并且每个结点没有左子结点,只有一个右子结点。
思路1 递归遍历
递归中序遍历,得到中序序列,然后建树:
class Solution { public: vector inorder; void inorderTraversal(TreeNode* root) { if (root) { inorderTraversal(root->left); inorder.push_back(root->val); inorderTraversal(root->right); } } void rebuild(TreeNode*& root, int idx) { if (idx < inorder.size()) { root = new TreeNode(inorder[idx++]); rebuild(root->right, idx); } } TreeNode* increasingBST(TreeNode* root) { inorderTraversal(root); TreeNode *newRoot; rebuild(newRoot, 0); return newRoot; }};
结果如下:
执行用时:4 ms, 在所有 C++ 提交中击败了63.16% 的用户内存消耗:7.2 MB, 在所有 C++ 提交中击败了31.83% 的用户
不进行收集,而是在递归遍历的时候直接建树,实际上是在用尾插法创建一个链表:
class Solution { public: TreeNode *rear; void inorderTraversalAndReBuild(TreeNode* root) { if (root) { inorderTraversalAndReBuild(root->left); rear->right = new TreeNode(root->val); rear = rear->right; inorderTraversalAndReBuild(root->right); } } TreeNode* increasingBST(TreeNode* root) { TreeNode dummy(0); rear = &dummy; inorderTraversalAndReBuild(root); return dummy.right; }};
思路2 非递归遍历
使用非递归方法+尾插法,代码如下:
class Solution { public: TreeNode* increasingBST(TreeNode* root) { if (root == nullptr) return root; TreeNode dummy(0), *rear = &dummy; stackst; while (root || !st.empty()) { while (root) { st.push(root); root = root->left; } root = st.top(); st.pop(); rear->right = new TreeNode(root->val); rear = rear->right; //尾插法 root = root->right; } return dummy.right; }};
效率如下:
执行用时:0 ms, 在所有 C++ 提交中击败了100.00% 的用户内存消耗:7.1 MB, 在所有 C++ 提交中击败了53.39% 的用户
转载地址:https://memcpy0.blog.csdn.net/article/details/108934212 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
逛到本站,mark一下
[***.202.152.39]2024年04月25日 01时02分18秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
java实现稀疏数组及将稀疏数组存入硬盘中
2019-04-30
2021-05-18
2019-04-30
基础架构系列篇-NGINX部署VUE
2019-04-30
基础架构系列篇-系统centos7安装kafka
2019-04-30
软件质量的8个特性
2019-04-30
2021年不可错过的17种JS优化技巧(一)
2019-04-30
在 Vue 中用 Axios 异步请求API
2019-04-30
MySQL进阶查询(SELECT 语句高级用法)
2019-04-30
Mysql 之主从复制
2019-04-30
【NLP学习笔记】中文分词(Word Segmentation,WS)
2019-04-30
对于时间复杂度的通俗理解
2019-04-30
如何输入多组数据并输出每组数据的和?
2019-04-30
行阶梯型矩阵
2019-04-30
MATLAB指定路径保存图片方法
2019-04-30
JAVA学习笔记6 - 数组
2019-04-30
【学习笔记】Android Activity
2019-04-30
location区段
2019-04-30
linux内存的寻址方式
2019-04-30
how2heap-double free
2019-04-30