前序、中序、后序遍历非递归

最新推荐文章于 2025-02-21 23:04:46 发布

原创最新推荐文章于 2025-02-21 23:04:46 发布 · 225 阅读

0 ·

CC 4.0 BY-SA版权

文章标签：

#leetcode

力扣经典习题专栏收录该内容

43 篇文章

订阅专栏

本文详细介绍了二叉树的三种遍历算法：前序遍历、中序遍历和后序遍历。通过使用栈结构，文章提供了实现这些遍历算法的C++代码示例，帮助读者深入理解二叉树的遍历过程。

1.前序遍历

/*
struct TreeNode{

       int val;
       TreeNode *left;
       TreeNode *right;
       TreeNode(int x):val(x),left(NULL),right(NULL){}

}
*/


vector<int> preorder(TreeNode* root){
       if(root==NULL) return {};
        
        stack<TreeNode*> s;
        TreeNode* cur=root;
        vector<int> res;

        while(!s.empty()||cur!=NULL){
            if(cur!=NULL){
                res.push_back(cur->val);
                s.push(cur);//先放根节点
                cur = cur->left;
            }
            else{
                cur =  s.top();
                cur = cur->right;
                s.pop();
            }
        }

        return res;
}

2.中序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if(root==NULL) return {};

        stack<TreeNode*> s;
        TreeNode* cur=root;
        vector<int> res;

        while(cur!=NULL||!s.empty()){
            if(cur!=NULL){
                s.push(cur);
                cur=cur->left;
            }
            else{
                cur = s.top();
                s.pop();
                res.push_back(cur->val);
                cur=cur->right;
            }
        }

        return res;
    }
};

3.后序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {

        if(root==NULL)return {};

        stack<TreeNode*> s1;
        stack<TreeNode*> s2;
        TreeNode *cur = root;
        vector<int> res;

        while(!s1.empty()||cur!=NULL){
            if(cur!=NULL){
                s1.push(cur);
                s2.push(cur);
                cur = cur->right;
            }
            else{
                cur = s1.top();
                s1.pop();
                cur = cur->left;
            }
        }

        while(!s2.empty()){
            res.push_back(s2.top()->val);
            s2.pop();
        }

        return res;
    }
};