Simple Coder: Binary Tree InorderTraversal

Sunday, November 2, 2014

Binary Tree InorderTraversal





Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},


   1
    \
     2
    /
   3




return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: Inorder in vector which contains node values.
     */
public:
   vector<int> inorderTraversal(TreeNode *root) {
        vector<int> output;
        stack<TreeNode *> st;
         
        while (root || !st.empty()){
            if (!root) {
                root = st.top();
                st.pop();
                output.push_back(root->val);
                root = root->right;
            }
            else {
                st.push(root);
                root = root->left;
            }
        }
         
        return output;
    }
};
 //Morris Traversal
 vector<int> inorderTraversal(TreeNode *root) {
         vector<int> output;
         
         while(root) { 
             if (root->left) {
                 TreeNode *prev = root->left;
                 while(prev->right != NULL && prev->right != root) 
                   prev = prev->right;
                   
                 if (!prev->right) {
                     prev->right = root;
                     root =root->left;
                  }
                  else {
                      prev->right = NULL;
                      output.push_back(root->val);
                      root = root->right;
                 }
             }
             else {
                 output.push_back(root->val);
                 root = root->right;
             }
         }
         
         return output;
    }
    class Solution {
    void pushLeft(TreeNode *root, stack<TreeNode *> &st) {
       while(root) {
           st.push(root);
           root = root->left;
       }
   }


class Solution {
    void pushLeft(TreeNode *root, stack<TreeNode *> &st) {
       while(root) {
           st.push(root);
           root = root->left;
       }
   }
   
public:
   vector<int> inorderTraversal(TreeNode *root) {
        vector<int> output;
        stack<TreeNode*> st;
        
        pushLeft(root, st);
        
        while (!st.empty()) {
            root = st.top();
            st.pop();
            output.push_back(root->val); 
            pushLeft(root->right, st);
        }

        return output;
    }
};

Simple Coder

Online Judge Solutions

Sunday, November 2, 2014

Binary Tree InorderTraversal

No comments:

Post a Comment