Leetcode 48: Binary Tree Inorder Traversal (C++)

Keys of this problem:

1. Binary tree. 

   You need to know what's a binary tree and what's inorder traversal. There are three kinds of traversal in Depth-First Traversal:

LVR: left-visit-right, also called inorder traversal;

LRV: left-visit-right, also called postorder traversal;

VLR: visit-left-right, also called preorder traversal;

2. Stack

  You need to familiar yourself with stack class first. In this problem, the stack is used to temporally store the previous node's pointers.  

3. Logic control
  How to control the logic to let it traversal the left and right nodes?!!

/**

* 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) {

              stack<TreeNode*> s;

              vector<int> result;

              while (!s.empty() || root != NULL){

                     //stack only and turn left

                     if (root != NULL){

                           s.push(root);

                           root = root->left;

                     }

                     else

                     {

                           //pop only and turn right

                           root = s.top();

                           result.push_back(root->val);

                           s.pop();

                           root = root->right;

                     }

              }

              return result;

       }

};