Binary Tree Inorder Traversal Problem Solution

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]

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;
}