听说递归能做的,栈也能做!

本文转载自微信公众号「代码随想录」,作者程序员Carl 。转载本文请联系代码随想录公众号。

二叉树的迭代遍历

看完本篇大家可以使用迭代法,再重新解决如下三道leetcode上的题目:

144.二叉树的前序遍历 94.二叉树的中序遍历 145.二叉树的后序遍历

为什么可以用迭代法(非递归的方式)来实现二叉树的前后中序遍历呢?

我们在栈与队列:匹配问题都是栈的强项中提到了,递归的实现就是:每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中,然后递归返回的时候,从栈顶弹出上一次递归的各项参数,所以这就是递归为什么可以返回上一层位置的原因。

此时大家应该知道我们用栈也可以是实现二叉树的前后中序遍历了。

前序遍历(迭代法)

我们先看一下前序遍历。

前序遍历是中左右,每次先处理的是中间节点,那么先将跟节点放入栈中,然后将右孩子加入栈,再加入左孩子。

为什么要先加入 右孩子,再加入左孩子呢?因为这样出栈的时候才是中左右的顺序。

动画如下:

不难写出如下代码: (注意代码中空节点不入栈)

class Solution { public:     vector<int> preorderTraversal(TreeNode* root) {         stack<TreeNode*> st;         vector<int> result;         if (root == NULL) return result;         st.push(root);         while (!st.empty()) {             TreeNode* node = st.top();                       // 中             st.pop();             result.push_back(node->val);             if (node->right) st.push(node->right);           // 右(空节点不入栈)             if (node->left) st.push(node->left);             // 左(空节点不入栈)         }         return result;     } }; 

此时会发现貌似使用迭代法写出前序遍历并不难,确实不难。

此时是不是想改一点前序遍历代码顺序就把中序遍历搞出来了?

其实还真不行!

但接下来,再用迭代法写中序遍历的时候,会发现套路又不一样了,目前的前序遍历的逻辑无法直接应用到中序遍历上。

中序遍历(迭代法)

为了解释清楚,我说明一下 刚刚在迭代的过程中,其实我们有两个操作:

处理:将元素放进result数组中

访问:遍历节点

分析一下为什么刚刚写的前序遍历的代码,不能和中序遍历通用呢,因为前序遍历的顺序是中左右,先访问的元素是中间节点,要处理的元素也是中间节点,所以刚刚才能写出相对简洁的代码,因为要访问的元素和要处理的元素顺序是一致的,都是中间节点。

那么再看看中序遍历,中序遍历是左中右,先访问的是二叉树顶部的节点,然后一层一层向下访问,直到到达树左面的最底部,再开始处理节点(也就是在把节点的数值放进result数组中),这就造成了处理顺序和访问顺序是不一致的。

那么在使用迭代法写中序遍历,就需要借用指针的遍历来帮助访问节点,栈则用来处理节点上的元素。

动画如下:

中序遍历,可以写出如下代码:

class Solution { public:     vector<int> inorderTraversal(TreeNode* root) {         vector<int> result;         stack<TreeNode*> st;         TreeNode* cur = root;         while (cur != NULL 
热点文章
近期更新
友情链接

Powered by 江门特福庆配件有限公司 @2018 RSS地图 HTML地图