C++ 图解二叉树非递归中序 + 实战力扣题

leetCode 94.二叉树的中序遍历 94. 二叉树的中序遍历 - 力扣（LeetCode）

算法思路：

总结： 对中序遍历这个例子进行总结，找出打印“中”节点的时刻，来寻找本质。打印的是一棵二叉树的“中”节点，那么当发现cur指向它的左边界的节点是空节点（NULL）。此时就可以打印它。“中节点”打印之后，让其cur指向其右孩子，重复这个过程

C++代码

// 非递归中序遍历
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*>st;
        TreeNode* cur = root;
        while(cur || !st.empty()) {
            // 指针来访问节点，访问到最底层
            if(cur) {
                st.push(cur);//将访问的节点放进栈
                cur=cur->left; //左
            } else{
                cur=st.top();//从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
                res.push_back(cur->val);
                st.pop();
                cur=cur->right;//右
            }
        }
        return res;
    }
};

我的B站讲解视频：
两分钟学会非递归中序遍历_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1294y1G7ka/?spm_id_from=333.999.0.0&vd_source=a934d7fc6f47698a29dac90a922ba5a3