LC94 Inorder Traversal of binary tree

Given a binary tree, return the inorder traversal of its nodes’ values.
In order traversal means visit the left, then the root, then the right.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int>res;
        recurTraverse(root, res);
        return res;
    }
    void recurTraverse(TreeNode* root, vector<int>& res){
        if(root == NULL) return;
        recurTraverse(root -> left, res);
        res.push_back(root -> val);
        recurTraverse(root -> right, res);
    }
};

Iterative solution

In this code, we will use a stack to keep track of parent nodes.
We will first put root and all its left child node push onto the stack. And once we finished pushing all left child, we will pop the stack, store its value to res. Then if the poped node has right child, in the next iteration, we will push it and all its left child onto the stack. This method will ensure left-middle-right order.

    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> parentStack;
        vector<int> res;
        TreeNode* currNode = root;
        while(!parentStack.empty() || currNode){
            if(currNode){
                parentStack.push(currNode);
                currNode = currNode -> left;
            }
            else{
                TreeNode* tempNode = parentStack.top();
                parentStack.pop();
                res.push_back(tempNode -> val);
                currNode = tempNode -> right;
            }
        }
        return res;
    }

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax