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);
add2p(*p, *sz, *n, node->val);
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);
add2p(p, sz, n, node->val);
node = node->right;
}
free(stack);
#endif
*returnSize = n;
return p;
}
Input
root = [1,null,2,3]
Output
[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);
}
};
Input
root = [1,null,2,3]
Output
[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();
result.add(removed.val);
TreeNode rightNode = removed.right;
while (rightNode != null) {
stack.push(rightNode);
rightNode = rightNode.left;
}
}
return result;
}
}
Input
root = []
Output
[]
#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);
}
}
Input
root = [1]
Output
[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
Input
root = [1]
Output
[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);
result.Add(node.val);
InorderTraversal(node.right, result);
}
}
}
Input
root = [1,null,2,3]
Output
[1,3,2]