LeetCode—94.二叉树的中序遍历[Binary Tree Inorder Traversal]——分析及代码[C++]

一、题目二、分析及代码1. 递归（1）思路（2）代码（3）结果 2. 迭代（1）思路（2）代码（3）结果 三、其他

一、题目

给定一个二叉树，返回它的中序 遍历。

示例:

输入: [1,null,2,3] 1 \ 2 / 3 输出: [1,3,2]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、分析及代码

1. 递归

（1）思路

遍历左子树 -> 记录根节点 -> 遍历右子树

（2）代码

class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> ans; inorderTraversal(ans, root); return ans; } void inorderTraversal(vector<int>& ans, TreeNode* root) { if (root == NULL) return; inorderTraversal(ans, root->left); ans.push_back(root->val); inorderTraversal(ans, root->right); } };

（3）结果

执行用时 ：4 ms, 在所有 C++ 提交中击败了 79.74% 的用户； 内存消耗 ：9.3 MB, 在所有 C++ 提交中击败了 40.38% 的用户。

2. 迭代

（1）思路

与递归解法实现过程的主要区别：用栈记录遍历过程中存储的根节点。

（2）代码

class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> ans; stack<TreeNode* > s; TreeNode* node = root; while (node != NULL || !s.empty()) { while (node != NULL) { s.push(node); node = node->left; } node = s.top(); ans.push_back(node->val); s.pop(); node = node->right; } return ans; } };

（3）结果

执行用时 ：0 ms, 在所有 C++ 提交中击败了 100% 的用户； 内存消耗 ：9 MB, 在所有 C++ 提交中击败了 85.74% 的用户。

三、其他

暂无。