LeetCode C++ 94. Binary Tree Inorder Traversal【二叉树/DFS】中等
发布日期:2021-07-01 02:51:56
浏览次数:2
分类:技术文章
本文共 2445 字,大约阅读时间需要 8 分钟。
Given the root of a binary tree, return the inorder traversal of its nodes’ values.
Follow up: Recursive solution is trivial, could you do it iteratively?
Example 1:
Input: root = [1,null,2,3]Output: [1,3,2]
Example 2:
Input: root = []Output: []
Example 3:
Input: root = [1]Output: [1]
Example 4:
Input: root = [1,2]Output: [2,1]
Example 5:
Input: root = [1,null,2]Output: [1,2]
Constraints:
- The number of nodes in the tree is in the range
[0, 100]
. -100 <= Node.val <= 100
题意:进行二叉树的中序遍历,返回元素序列。
思路1
中序递归遍历,很简单的代码:
class Solution { public: vector ans; vector inorderTraversal(TreeNode* root) { if (root) { inorderTraversal(root->left); ans.push_back(root->val); inorderTraversal(root->right); } return ans; }};
效率如下:
执行用时:0 ms, 在所有 C++ 提交中击败了100.00% 的用户内存消耗:10.1 MB, 在所有 C++ 提交中击败了5.01% 的用户
思路2
非递归中序遍历,教科书式的写法:
class Solution { public: vector inorderTraversal(TreeNode* root) { if (root == nullptr) return vector (); vector ans; stackst; TreeNode *cur = root; while (cur || !st.empty()) { while (cur) { st.push(cur); cur = cur->left; } cur = st.top(); st.pop(); ans.push_back(cur->val); cur = cur->right; } return ans; }};
效率如下:
执行用时:0 ms, 在所有 C++ 提交中击败了100.00% 的用户内存消耗:8.3 MB, 在所有 C++ 提交中击败了8.06% 的用户
思路3
模拟系统栈的调用。代码如下:
class Solution { public: struct command { TreeNode *node; int instruction; command(int i = 0, TreeNode *t = nullptr) : instruction(i), node(t) { } }; vector inorderTraversal(TreeNode* root) { if (root == nullptr) return vector (); vector ans; stackst; st.push(command(1, root)); while (!st.empty()) { command t = st.top(); st.pop(); if (t.instruction == 0) { ans.push_back(t.node->val); } else { if (t.node->right) st.push(command(1, t.node->right)); st.push(command(0, t.node)); if (t.node->left) st.push(command(1, t.node->left)); } } return ans; }};
效率较低:
执行用时:4 ms, 在所有 C++ 提交中击败了46.11% 的用户内存消耗:8.5 MB, 在所有 C++ 提交中击败了6.20% 的用户
转载地址:https://memcpy0.blog.csdn.net/article/details/108733537 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
网站不错 人气很旺了 加油
[***.192.178.218]2024年05月07日 03时13分33秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Unix环境变量--堆和栈的区别
2019-05-02
Unix环境变量--POSIX异步I/O
2019-05-02
UNIX环境变量--读写函数变体
2019-05-02
UNIX环境变量--存储映射I/O
2019-05-02
UNIX环境变量--IPC之管道通信
2019-05-02
C++虚继承【详解】
2019-05-02
tinyhttpd源码学习1
2019-05-02
Plus One
2019-05-02
Linux内核完全剖析0.12(一)
2019-05-02
Sum Root to Leaf Numbers
2019-05-02
Pascal's Triangle
2019-05-02
ffmpeg提取音频存为PCM
2019-05-02
我也学android(1)搭个环境
2019-05-02
Reverse Linked List II
2019-05-02
最长递增子序列
2019-05-02
题目1511:从尾到头打印链表
2019-05-02
Web Bench 源码学习1
2019-05-02
Search Insert Position
2019-05-02
Length of Last Word
2019-05-02
QuickSort快速排序
2019-05-02