LeetCode Hot 100 P94 Binary Tree Inorder Traversal

---

Timeline

Timeline

2026-03-14

init

Binary Tree

---

Problem:

P94 Binary Tree Inorder Traversal

https://leetcode.cn/problems/binary-tree-inorder-traversal/description/?envType=study-plan-v2&envId=top-100-liked

It uses a non-recursive implementation

struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode()
                : val(0)
                , left(nullptr)
                , right(nullptr)
        {
        }
        TreeNode(int x)
                : val(x)
                , left(nullptr)
                , right(nullptr)
        {
        }
        TreeNode(int x, TreeNode *left, TreeNode *right)
                : val(x)
                , left(left)
                , right(right)
        {
        }
};

#include <vector>
#include <stack>
using std::stack;
using std::vector;

class Solution {
    public:
        vector<int> inorderTraversal(TreeNode *root)
        {
                stack<TreeNode *> stk;
                TreeNode *p = root;
                vector<int> ret;

                while (p || !stk.empty()) {
                        if (p) {
                                stk.push(p);
                                p = p->left;
                        } else {
                                p = stk.top();
                                stk.pop();
                                ret.push_back(p->val); // visit p
                                p = p->right;
                        }
                }

                return ret;
        }
};