题目描述

题目链接：94. Binary Tree Inorder Traversal

Given the root of a binary tree, return the inorder traversal of its nodes' values.

例子

例子 1

Input: root = [1,null,2,3] Output: [1,3,2]

例子 2

Input: root = [] Output: []

例子 3

Input: root = [1] Output: [1]

例子 4

Input: root = [1,2] Output: [2,1]

例子 5

Input: root = [1,null,2] Output: [1,2] Explanation:

Constraints

.The number of nodes in the tree is in the range [0, 100]. .-100 <= Node.val <= 100

Follow Up

Recursive solution is trivial, could you do it iteratively?

解题思路

这道题要求输出二叉树的中序遍历，同样可以利用栈来解决。首先不停往栈中压入所有左节点（相当于树的最左侧），然后从栈顶取出节点再取其右节点进行重复操作。代码如下：

#include <stack>
#include <vector>

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        std::vector<int> result;
        if (!root) return result;

        std::stack<TreeNode*> s;
        TreeNode* curr = root;
        while (!s.empty() || curr) {
            while (curr) {
                s.push(curr);
                curr = curr->left;
            }

            curr = s.top();
            s.pop();
            result.push_back(curr->val);
            curr = curr->right;
        }

        return result;
    }
};

• 时间复杂度: O(n)
• 空间复杂度: O(h)

GitHub 代码同步地址： 94.BinaryTreeInorderTraversal.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions