## [Leetcode]94. Binary Tree Inorder Traversal(C++)

### 题目描述

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`

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

Built with Hugo
Theme Stack designed by Jimmy