[leetcode] 94. Binary Tree Ignor

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

For example:

Given binary tree [1,null,2,3],
   1
    \
     2
    /
   3
return [1,3,2].

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

解题思路:
二叉树的遍历是基础，具体至少应该掌握递归遍历和迭代遍历，遍历又分别前序遍历，中序遍历和后续遍历。代码如下：

递归方法：

class Solution {
public:
    void getInorderData(TreeNode* root, vector<int> & ret)
    {
        if(root == NULL) return;
        if(root->left != NULL) getInorderData(root->left,ret);
        ret.push_back(root->val);
        if(root->right != NULL) getInorderData(root->right,ret);
        return;
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        getInorderData(root,ret);
        return ret;
    }
};

迭代版本：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
       vector<int> ret;
       stack<TreeNode*> stk;
       TreeNode* curr = root;
       
       while(!stk.empty() || curr)
       {
           if(curr)
           {
               stk.push(curr);
               curr = curr->left;
           }else
           {
               curr = stk.top();
               ret.push_back(curr->val); //永远在当前节点是根节点的时候取值
               stk.pop();
               curr = curr->right;
           }
       }
       
       return ret;
    }
};

参考资料：https://discuss.leetcode.com/topic/3288/three-methods-to-solve-c