LeetCode刷题(19)【简单】二叉树的前&&中&&后遍历(非递归)(C++)

半生瓜的blog

发布于 2023-05-13 13:35:10

1760

发布于 2023-05-13 13:35:10

文章被收录于专栏：半生瓜のblog

精华在于进栈和出栈的时机

94.二叉树的中序遍历

题目

思路：中序遍历的顺序是，左 - 根 - 右创建一个栈来存储结点，创建一个vector来存储中序遍历的值从根结点开始，只要该结点有左子树，就将该结点压进栈中。直到root为空。取出栈顶元素，栈顶元素出栈，将该结点值存进recv。 … 剩下的只可意会不可言传了，

感谢这位老哥分享——链接

class Solution {
public:
    //中序遍历顺序-左-中-右
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int>recv;
        stack<TreeNode*> Tstack;
       
       //当前结点不为空或当前栈不为空
       while(root || !Tstack.empty())
       {
           while(root)
           {
               //只要当前结点不为空就往栈里面压
               Tstack.push(root);
               root = root->left;
           }
           //此时栈顶元素为根节点左侧树最左的左子树
           //取到该结点
           root = Tstack.top();
           Tstack.pop();
           //pop出栈，存进recv中
           recv.push_back(root->val);
           root = root->right;
       }
        return recv;
    }
};

递归方法

144.二叉树的前序遍历

题目

非递归 感谢这位老哥分享——链接

class Solution {
public:
    
    vector<int> preorderTraversal(TreeNode* root) {
    vector<int>recv;
    stack<TreeNode*>Tstack;
    while(root || !Tstack.empty())
    {
        while(root)
        {
            recv.push_back(root->val);
            Tstack.push(root);
            root = root->left;
        }
        root = Tstack.top();
        Tstack.pop();
        root = root->right;
    }    
    return recv;
    }
};

145.二叉树的后序遍历

题目

一直往栈里面往左节点，压到左边最后一个做结点，往回pop,判断当前这个结点是否右结点，有右结点就输出，最后判断自己。

感谢这位老哥分享思路—链接

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int>result;
        stack<TreeNode*>Tstack;
        TreeNode* cur = root;
        TreeNode* prev = nullptr;//记录cur上一个指向的结点，比cur走慢一步

        while(!Tstack.empty() || cur)
        {
            //只有cur不为空，就一直往里面压左节点
            while(cur) 
            {
                Tstack.push(cur);
                cur =cur->left;
            }
            cur = Tstack.top();
            //如果当前结点没有右结点 ||  右结点已经访问过了
            if(!cur->right || prev == cur->right)
            {
                Tstack.pop();
                result.push_back(cur->val);
                prev = cur;
                //要从栈里面往外面吐结点，所以要将cur置为null
                cur = nullptr;
            }   
            else
            {
                cur = cur->right;
            }
        }
        return   result;
    }
};

大致流程感觉