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


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment