[LeetCode] 94. 二叉树的中序遍历

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

思路:

输出顺序为：左节点->根节点->右节点，使用栈暂存即可

AC代码:

/**
 * 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) {
        vector<int> result;
        stack<TreeNode*> nodeStack;
        if(root == NULL)
        {
            return result;
        }
        while(root || !nodeStack.empty())
        {
            while(root)
            {
                nodeStack.push(root);
                root = root->left;
            }
            root = nodeStack.top();
            nodeStack.pop();
            result.push_back(root->val);
            root = root->right;
        }
        return result;
    }
};Code language: C++ (cpp)