【二叉树】风格统一，简单易记的二叉树非递归遍历

77 阅读 0 评论 51 点赞

我是靠谱客的博主慈祥柚子，最近开发中收集的这篇文章主要介绍【二叉树】风格统一，简单易记的二叉树非递归遍历，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

二叉树递归遍历的缺点很多，函数跳转拖慢速度，二叉树深度大时还会导致爆栈。相较之下非递归遍历就没有这些问题，但网络上的三种非递归遍历代码并没有做到递归代码那种程度的风格统一，易于理解（同一个人写的三种非递归遍历之间变量数、判断体中的语句数均各有不同，而递归遍历之间只是访问节点的位置不同，其他部分可以完全一致），因此我决定做一个简单归纳，让非递归代码也能像递归代码那样风格统一，便于记忆。

注意：我的算法与网络上大部分算法相比付出了额外的空间，请读者自行取舍。

原题地址

前序中序后序

代码

class Solution {
public:
    typedef TreeNode *np;
    typedef pair<np,bool> mark;
    //前序遍历
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        if(!root){
            return result;
        }
        stack<pair<np,bool>> data;
        data.push(mark(root,false));
        while(!data.empty()){
            if(!data.top().second){
                np temp = data.top().first;
                data.pop();
                if(temp->right){
                    data.push(mark(temp->right,false));
                }
                if(temp->left){
                    data.push(mark(temp->left,false));
                }
                data.push(mark(temp,true));//注意这行的位置变化
            }else{
                result.push_back(data.top().first->val);
                data.pop();
            }
        }
        return result;
    }
    //中序遍历
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        if(!root){
            return result;
        }
        stack<pair<np,bool>> data;
        data.push(mark(root,false));
        while(!data.empty()){
            if(!data.top().second){
                np temp = data.top().first;
                data.pop();
                if(temp->right){
                    data.push(mark(temp->right,false));
                }
                data.push(mark(temp,true));//注意这行的位置变化
                if(temp->left){
                    data.push(mark(temp->left,false));
                }
            }else{
                result.push_back(data.top().first->val);
                data.pop();
            }
        }
        return result;
    }
    //后序遍历
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        if(!root){
            return result;
        }
        stack<pair<np,bool>> data;
        data.push(mark(root,false));
        while(!data.empty()){
            if(!data.top().second){
                np temp = data.top().first;
                data.pop();
                data.push(mark(temp,true));//注意这行的位置变化
                if(temp->right){
                    data.push(mark(temp->right,false));
                }
                if(temp->left){
                    data.push(mark(temp->left,false));
                }
            }else{
                result.push_back(data.top().first->val);
                data.pop();
            }
        }
        return result;
    }
};

mark.second记录了这个节点有没有被访问过，有了这条信息就可以很方便的写出风格统一的代码。

1.将mark(root,false)入栈
2.从原理上栈中节点指针不可能为NULL，因此程序必须事先判断root是否为NULL。
3.如果栈顶节点未访问过，则将其按各自的规律展开：
前序：栈顶……原节点……栈底 => 栈顶…… 原节点、左孩子、右孩子……栈底
中序：栈顶……原节点……栈底 => 栈顶…… 左孩子、原节点、右孩子……栈底
后序：栈顶……原节点……栈底 => 栈顶…… 左孩子、右孩子、原节点……栈底
展开时，如果left或right为NULL，则不压入任何东西
如果栈顶节点已经访问过一次，则将val记录后出栈
4.重复上一步直到栈为空

当然，代码中有几处是可以简化的，为了保持整齐我就没有进行省略。
如果可以在保持整齐的前提下进行优化（主要是空间上），欢迎评论指出