二叉树的中序遍历

描述

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：

输入：root = []
输出：[]
示例 3：

输入：root = [1]
输出：[1]

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/binary-tree-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

C++代码

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

// 定义二叉树的结构体
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) {
        vector<int> res;  // 存储结果的vector
        stack<TreeNode*> s;  // 存储节点的栈
        TreeNode* curr = root;  // 当前遍历到的节点

        while (curr != NULL || !s.empty()) {  // 当节点不为空或栈不为空时
            while (curr != NULL) {  // 将左子树的所有节点压入栈中
                s.push(curr);
                curr = curr->left;
            }
            curr = s.top();  // 取出栈顶元素
            s.pop();
            res.push_back(curr->val);  // 将该节点的值存入结果vector中
            curr = curr->right;  // 遍历右子树
        }

        return res;  // 返回结果vector
    }
};

int main() {
    // 构造二叉树
    TreeNode* root = new TreeNode(1);
    root->right = new TreeNode(2);
    root->right->left = new TreeNode(3);

    // 创建Solution对象
    Solution s;
    // 调用inorderTraversal函数
    vector<int> res = s.inorderTraversal(root);
    // 输出结果
    for (int i = 0; i < res.size(); i++) {
        cout << res[i] << " ";
    }
    cout << endl;

    return 0;
}

1. 定义了二叉树的结构体，包含节点的值，左右子节点指针。
2. 创建了一个Solution类，其中inorderTraversal函数用于实现二叉树的中序遍历。
3. 在inorderTraversal函数中，定义了一个vector用于存储遍历结果，定义了一个栈用于存储节点，定义了一个指针指向当前遍历到的节点。
4. 当节点不为空或栈不为空时，进入循环。
5. 将左子树的所有节点压入栈中。
6. 取出栈顶元素，将该节点的值存入结果vector中。
7. 遍历右子树。
8. 返回结果vector。
9. 在main函数中，构造了一个二叉树，创建了一个Solution对象，调用inorderTraversal函数并输出结果。