二叉树的遍历（递归+非递归）

二叉树的遍历（递归+非递归） 二叉树的遍历（递归+非递归）

本文为大家展示了二叉树的两种遍历方法，可以方便我们在日常刷题时提供一个基础模板，如果有哪些不对的地方欢迎评论区指出~

---

文章目录

• 二叉树的遍历（递归+非递归）
• 一、递归遍历
• 二、非递归遍历（栈）
• 三、层序遍历（队列）
• 总结

---

一、递归遍历

代码如下：

    TreeNode* TreeDepth(TreeNode* pRoot)
    {
        if (!pRoot) return 0;
        queue q;
        q.push(pRoot);
        while (!q.empty()) {
            int sz = q.size();
            while (sz--) {
                TreeNode* node = q.front(); q.pop();
                
                if (node->left)  q.push(node->left);
                
                if (node->right) q.push(node->right);
            }
        }
        return NULL;
    }

示例：pandas 是基于NumPy 的一种工具，该工具是为了解决数据分析任务而创建的。

二、非递归遍历（栈）

代码如下：

    vector pre;
    vector mid;
    vector post;
    vector > threeOrders(TreeNode* root) {
        if(root != nullptr){//nullptr任意指针类型
            preorder(root);
            midorder(root);
            postorder(root);
        }
        vector>res = {pre,mid,post};
        return res;
    }
    vector preorder(TreeNode* root) {//中左右
        if(root==NULL){
            return pre;
        }
        stack tmp;//设置栈对象
        tmp.push(root);//保存根结点
        while(!tmp.empty()){
            auto x = tmp.top();
            tmp.pop();//出栈
            pre.push_back(x->val);//存入容器
            if(x->right){
                tmp.push(x->right);
            }
            if(x->left){
                tmp.push(x->left);
            }
        }
        return pre;
    }
    vector midorder(TreeNode* root) {//左中右
        stack s;//设置栈对象
        while (s.size() || root){
            while (root){
                s.push(root);
                root = root->left;//先左
            }
            if (s.size()){
                root = s.top();
                s.pop();
                mid.push_back(root->val);
                root = root->right;
            }
        }
        return mid;
	}
    vector postorder(TreeNode* root) {//左右中
        if(root==NULL){
            return post;
        }
        stack tmp;//设置栈对象
        tmp.push(root);
        while(!tmp.empty()){
            auto x = tmp.top();
            tmp.pop();
            post.push_back(x->val);
            if(x->left){
                tmp.push(x->left);
            }
            if(x->right){
                tmp.push(x->right);
            }
        }
        reverse(post.begin(),post.end());
        return post;
    }

三、层序遍历（队列）

代码如下：

    TreeNode* TreeTraversal(TreeNode* pRoot)
    {
        if (!pRoot) return 0;
        queue q;
        q.push(pRoot);
        while (!q.empty()) {
            int sz = q.size();
            while (sz--) {
                TreeNode* node = q.front(); q.pop();
                
                if (node->left)  q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        return NULL;
    }

---

总结 以上就是今天要讲的内容，本文仅仅简单介绍了二叉树的遍历，可以方便我们在日常刷题时提供一个基础模板，如果有哪些不对的地方欢迎评论区指出~