前言
二叉树的前序遍历
法一:递归;可以参考我之前写的博客:深入递归对递归有详细介绍.
class Solution { public: //中左右 vector<int> sz; vector<int> preorderTraversal(TreeNode* root) { if(root==nullptr)//结束条件 { return sz; } sz.push_back(root->val);//根 preorderTraversal(root->left);//左 preorderTraversal(root->right);//右 return sz; } };
法二:迭代法
我们先看一下前序遍历。
前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。
为什么要先加入 右孩子，再加入左孩子呢？ 因为这样出栈的时候才是中左右的顺序。
动画如下：
class Solution { public: //根左右 vector<int> preorderTraversal(TreeNode* root) { vector<int> sz; stack<TreeNode*> az; if(root==nullptr) { return sz; } az.push(root); while(!az.empty()) { TreeNode* node=az.top(); //根 az.pop(); sz.push_back(node->val); if(node->right)az.push(node->right);//右 if(node->left)az.push(node->left);//左 } return sz; } };
法一:递归
class Solution { public: vector<int> sz; vector<int> inorderTraversal(TreeNode* root) { if(root==nullptr) { return sz; } inorderTraversal(root->left); sz.push_back(root->val); inorderTraversal(root->right); return sz; } };
法二:迭代
为了解释清楚，我说明一下 刚刚在迭代的过程中，其实我们有两个操作：
- 处理：将元素放进sz数组中
- 访问：遍历节点
分析一下为什么刚刚写的前序遍历的代码，不能和中序遍历通用呢，因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。
那么再看看中序遍历，中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进sz数组中），这就造成了处理顺序和访问顺序是不一致的。
那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。
动画如下：
class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> az; stack<TreeNode*> sz; while(root!=nullptr||!sz.empty()) { while(root!=nullptr) { sz.push(root); root=root->left; } root=sz.top(); sz.pop(); az.push_back(root->val); root=root->right; } return az; } };
二叉树的后序遍历
法一:递归
class Solution { public: vector<int> az; vector<int> postorderTraversal(TreeNode* root) { if(root==nullptr) { return az; } postorderTraversal(root->left); postorderTraversal(root->right); az.push_back(root->val); return az; } };
法二:迭代
再来看后序遍历，先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了，如下图：
class Solution { public: vector<int> postorderTraversal(TreeNode* root) { vector<int> az; stack<TreeNode*> sz; if(root==nullptr) { return az; } sz.push(root); while(!sz.empty()) { TreeNode *node=sz.top(); sz.pop(); az.push_back(node->val); if(node->left) sz.push(node->left); if(node->right)sz.push(node->right); } reverse(az.begin(),az.end()); return az; } };
