---
tags: leetcode
---
# [94. Binary Tree Inorder Traversal](https://leetcode.com/problems/binary-tree-inorder-traversal)
---
# My Solution
## Solution 1: DFS (recursion)
### The Key Idea for Solving This Coding Question
### C++ Code
```cpp=
/**
* Definition for a binary tree node.
* 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) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
dfs(root);
return inorder;
}
private:
vector<int> inorder;
void dfs(TreeNode *root) {
if (root == nullptr) {
return;
}
dfs(root->left);
inorder.push_back(root->val);
dfs(root->right);
}
};
```
### Time Complexity
$O(n)$
$n$ is the number of nodes in the binary tree.
### Space Complexity
$O(H)$
$H$ is the height of the binary tree.
## Solution 2: DFS (iteration, stack)
### The Key Idea for Solving This Coding Question
### C++ Code
```cpp=
/**
* Definition for a binary tree node.
* 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) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
stack<TreeNode *> st;
vector<int> inorder;
while (!st.empty() || root != nullptr) {
if (root != nullptr) {
st.push(root);
root = root->left;
} else {
root = st.top();
st.pop();
inorder.push_back(root->val);
root = root->right;
}
}
return inorder;
}
};
```
### Time Complexity
$O(n)$
$n$ is the number of nodes in the binary tree.
### Space Complexity
$O(H)$
$H$ is the height of the binary tree.
## Solution 3: Morris Traversal
### The Key Idea for Solving This Coding Question
1. 找到每個 non-leaf 之子樹樹根 (以 `node` 指標指向它) 的 predecessor (以 `prev` 指標指向它)。此時，這個 predecessor 必無右子樹 (或右節點)。將 predecessor 的 `right` 指標指向 `node` 。在我們走訪完左子樹中的所有節點後，可由此時 predecessor 的 `right` 指標回到目前 `node` 所指向的節點。所以這個演算法會走訪每個節點兩次。
2. 第 21 ~ 22 行是 `node` 所指向的節點沒有左子樹。此時，可以直接將節點的數值推入 `inorder` ，然後走向 `node` 所指向之節點的右子樹。
3. 第 25 ~ 27 行的 `while` 迴圈是在尋找 `node` 的 predecessor ，以 `prev` 指標指向它。
4. 第 25 ~ 27 行的 `if-else` 中，若 `prev->right` 為 `nullptr` ，表示 `node` 第一次走訪此節點。反之，表示 `node` 的左子樹已走訪完畢，可以把 `node` 所指向之節點的值推入 `inorder` ，往 `node` 所指向之節點的右子樹走。
### C++ Code
```cpp=
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
*
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
* TreeNode(int val, TreeNode *left, TreeNode *right) : val(val), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> inorder;
TreeNode *node = root;
while (node) {
if (!node->left) {
inorder.push_back(node->val);
node = node->right;
} else {
TreeNode *prev = node->left;
while (prev->right != nullptr && prev->right != node) {
prev = prev->right;
}
if (prev->right == nullptr) {
prev->right = node;
node = node->left;
} else {
inorder.push_back(node->val);
prev->right = nullptr;
node = node->right;
}
}
}
return inorder;
}
};
```
### Time Complexity
$O(n)$
$n$ is the number of nodes in the binary tree.
### Space Complexity
$O(1)$
# Miscellaneous
[144. Binary Tree Preorder Traversal](https://leetcode.com/problems/binary-tree-preorder-traversal/)
[145. Binary Tree Postorder Traversal](https://leetcode.com/problems/binary-tree-postorder-traversal)
# Test Case
```
[1,null,2,3]
```
```
[1,2,3,4,5,null,8,null,null,6,7,9]
```
```
[]
```
```
[1]
```
```
[4,2,7,1,3]
```
```
[18,2,22,null,null,null,63,null,84,null,null]
```
```
[18,6,22,5,7,11,63,1,2,9,8,10,24,12,84]
```
```
[2,3,null,1]
```
```
[1,2,3]
```
```
[4,2,1,3,7]
```
```
[18,2,22,63,84]
```
```
[18,6,5,1,2,7,9,8,22,11,10,24,63,12,84]
```
-->
Sign in with Wallet
Connect another wallet