Algorithm

Problem Nmae: 94. Binary Tree Inorder Traversal

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

Example 1:

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

Example 2:

```Input: root = []
Output: []
```

Example 3:

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

Constraints:

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

Code Examples

#1 Code Example with C Programming

```Code - C Programming```

``````
#define add2p(P, SZ, N, V) do { \
if (SZ = N) { \
SZ *= 2; \
P = realloc(P, (SZ) * sizeof(int)); \
/* assert(P); */ \
} \
(P)[(N) ++] = V; \
} while (0)

void inorder(int **p, int *sz, int *n, struct TreeNode *node) {
if (!node) return;
inorder(p, sz, n, node->left);
inorder(p, sz, n, node->right);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
int sz, n, *p;
struct TreeNode **stack, *node;
int ssz, sp;

sz = 100;
p = malloc(sz * sizeof(int));
//assert(p);
n = 0;

#if 0
inorder(&p, &sz, &n, root);
#else
ssz = 100;
stack = malloc(ssz * sizeof(struct TreeNode *));
//assert(stack);
sp = 0;

#define PUSH(N) do { \
if (ssz == sp) { \
ssz *= 2; \
stack = realloc(stack, ssz * sizeof(struct TreeNode *)); \
/* assert(stack); */ \
} \
stack[sp ++] = N; \
} while (0)

#define POP(N) do { N = stack[-- sp]; } while (0)

node = root;
while (node || sp) {
while (node) {
PUSH(node);
node = node->left;
}
POP(node);
node = node->right;
}

free(stack);
#endif

*returnSize = n;
return p;
}
``````
Copy The Code &

Input

cmd
root = [1,null,2,3]

Output

cmd
[1,3,2]

#2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int>res;
/**
* Recursive.
* inorder(res, root);
* return res;
*/
if(!root) return res;
stack < TreeNode*>s;
TreeNode* cur = root;
while(!s.empty() || cur){
while(cur->left){
s.push(cur);
cur = cur->left;
}
res.push_back(cur->val);
cur = cur->right ? cur->right : NULL;
while(!cur && !s.empty()){
res.push_back(s.top()->val);
cur = s.top()->right ? s.top()->right : NULL;
s.pop();
}
}
return res;
}

void inorder(vector<int>& res, TreeNode* root){
if(!root) return;
inorder(res, root->left);
res.push_back(root->val);
inorder(res, root->right);
}
};
``````
Copy The Code &

Input

cmd
root = [1,null,2,3]

Output

cmd
[1,3,2]

#3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public List inorderTraversal(TreeNode root) {
if (root == null) {
return List.of();
}
Stack < TreeNode> stack = new Stack<>();
while (root != null) {
stack.push(root);
root = root.left;
}
List < Integer> result = new ArrayList<>();
while (!stack.isEmpty()) {
TreeNode removed = stack.pop();
TreeNode rightNode = removed.right;
while (rightNode != null) {
stack.push(rightNode);
rightNode = rightNode.left;
}
}
return result;
}
}
``````
Copy The Code &

Input

cmd
root = []

Output

cmd
[]

#4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const inorderTraversal = function(root) {
const res = [];
if (root == null) return res;
traversal(root, res);
return res;
};

function traversal(node, res) {
if (node.left) {
traversal(node.left, res);
}
res.push(node.val);
if (node.right) {
traversal(node.right, res);
}
}
``````
Copy The Code &

Input

cmd
root = [1]

Output

cmd
[1]

#5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
self.res = []
def dfs(node):
if not node: return
dfs(node.left)
self.res.append(node.val)
dfs(node.right)
dfs(root)
return self.res
``````
Copy The Code &

Input

cmd
root = [1]

Output

cmd
[1]

#6 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;

namespace LeetCode
{
public class _094_BinaryTreeInorderTraversal
{
public IList < int> InorderTraversal(TreeNode root)
{
IList<int> result = new List<int>();
InorderTraversal(root, result);
return result;
}

public void InorderTraversal(TreeNode node, IList < int> result)
{
if (node == null) return;

InorderTraversal(node.left, result);
InorderTraversal(node.right, result);
}
}
}
``````
Copy The Code &

Input

cmd
root = [1,null,2,3]

Output

cmd
[1,3,2]