阅读量:3
leetcode94. 二叉树的中序遍历
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
一般思路：我们当初在学数据结构时的方法就是递归解决。先递归遍历左子树，然后递归访问根节点，最后递归遍历右子树。所谓中序、先序、后序的递归遍历只需要更改res.push_back(node->val);
的位置即可。
完整代码如下：
class Solution { public: void inorder(TreeNode* node,vector<int> &res) { if(!node) return ; inorder(node->left,res); res.push_back(node->val); inorder(node->right,res); return ; } vector<int> inorderTraversal(TreeNode* root) { vector<int> res; if(root==NULL) return res; inorder(root,res); return res; } }; 我们可以将递归改写成迭代。
所谓迭代法，我们要使用到栈数据结构。具体来说，中序遍历就是把左子树的所有节点存入栈中，到底后再一个个弹出来，弹出来的过程中每弹出来一个，把根遍历后，把根的右子树也都存入栈中
class Solution { public: vector<int> inorderTraversal(TreeNode* root) { stack<TreeNode*> stk; vector<int> res; while(root!=nullptr || !stk.empty()) { while(root!=nullptr) { stk.push(root); root=root->left; } root=stk.top(); stk.pop(); res.push_back(root->val); root=root->right; } return res; } }; 迭代法里比较难理解的是对右子树的处理，当左子树节点都被存入栈中之后，我们弹出一个节点，将其放入结果数组后，再处理当前节点的右节点（如果有的话），因为当前节点的右节点也可能存在左节点，如果有的话这些节点应该是在栈中其他节点之前被遍历的。
二叉树的前序遍历迭代法的逻辑也是这样,唯一区别每次节点入栈之前先遍历到结果数组里。
代码如下：
class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> res; if (root == nullptr) { return res; } stack<TreeNode*> stk; TreeNode* node = root; while (!stk.empty() || node != nullptr) { while (node != nullptr) { res.push_back(node->val); stk.push(node); node = node->left; } node = stk.top(); stk.pop(); node = node->right; } return res; } }; 后序遍历迭代法相对将要难一些，我们之后再说。
