开发者社区云计算文章正文

二叉树的统一迭代遍历法

2024-01-11 29

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 二叉树的统一迭代遍历法

访问到一个结点后就将其右中左压入栈中，中就是其本身，也是父节点的左或者右儿子

由于访问的节点与要处理的节点不一定一致，所以在访问节点后加入null空节点来对访问节点做标记

此代码是中序遍历改下顺序即可变成其他遍历

vector<int> orderTraversal(TreeNode* root) {
        stack<TreeNode*> s;
        vector<int> result;
        if(!root) return result;
        else s.push(root);
        while(!s.empty()){
            TreeNode *curPtr = s.top();
            if(curPtr){
                s.pop();
/*  只需要改变他们的顺序即可决定是前序、后序还是中序
                if(curPtr->right) s.push(curPtr->right);  //右
                s.push(curPtr);  //中
                s.push(nullptr); //中
                if(curPtr->left) s.push(curPtr->left);    //左
*/
            }else{
                s.pop();
                curPtr = s.top();
                result.push_back(curPtr->val);
                s.pop();
            }
        }
        return result;
    }