Binary Tree Inorder Traversal Problem: Given the root
of a binary tree, return the inorder traversal of its nodes’ values.
Input: root = [1,null,2,3] Output: [1,3,2]
Table of Contents
Binary Tree Inorder Traversal Problem Solution
Problem Solution In Python
from collections import deque
class Solution(object):
def _in_order_iter(self, root):
stack = deque()
while stack or root:
if root:
stack.append(root)
root = root.left
else:
root = stack.pop()
yield root.val
root = root.right
def inorderTraversal(self, root):
return list(self._in_order_iter(root))
Problem Solution In Java
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> resultList = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode current = root;
while (current != null || !stack.isEmpty()) {
while (current != null) {
stack.push(current);
current = current.left;
}
current = stack.pop();
resultList.add(current.val);
current = current.right;
}
return resultList;
}
Problem Solution In C++
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> s;
vector<int> res;
do{
while(root!=NULL){
s.push(root);
root=root->left;
}
if(!s.empty()){
root=s.top();
s.pop();
res.push_back(root->val);
root=root->right;
}
}while(root!=NULL||!s.empty());
return res;
}
};
Problem Solution In C
int *ans;
int cnt;
int base;
void tra(struct TreeNode *node){
if(node==NULL){
return;
}
tra(node->left);
if(cnt==base){
//not enough memory
base*=2;
ans=realloc(ans,base*sizeof(int));
}
ans[cnt++]=node->val;
tra(node->right);
}
int* inorderTraversal(struct TreeNode* root, int* rs){
base=8;
ans=malloc(sizeof(int)*base);
cnt=0;
tra(root);
*rs=cnt;
return ans;
}