1. Binary Tree Inorder Traversal My Submissions QuestionEditorial Solution
   
   Total Accepted: 123484 Total Submissions: 310732 Difficulty: Medium
   
   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?

思路：1.递归

2.迭代

class Solution {

public:

    vector<int> inorderTraversal(TreeNode* root) {

        vector<int> v;

        if(root==NULL)return v;

        vector<int> vl,vr;

        vl = inorderTraversal(root->left);

        v.push_back(root->val);

        vr = inorderTraversal(root->right);

        int n = vl.size()+v.size()+vr.size();

        vector<int> res(n);

        copy(vl.begin(),vl.end(),res.begin());

        copy(v.begin(),v.end(),res.begin()+vl.size());

        copy(vr.begin(),vr.end(),res.begin()+vl.size()+v.size());

        return res;

    }

};

以下是迭代方法，多练习以写出一个精简的迭代代码

思路找到左线压入栈，自底向上访问，有右子树的节点跳至右子树重复

上述过程。

class Solution {

public:

    vector<int> inorderTraversal(TreeNode* root) {

        vector<int> v;

        stack<TreeNode*> st;

        while(root||!st.empty()){//第一个处理root情况

            while(root!=NULL){  //一直找到最左下角，没有的话后面弹出该元素值

                st.push(root);

                root = root->left;

            }

            root = st.top();

            st.pop();

            v.push_back(root->val);//弹出值，转至右子树

            root = root->right;

        }

        return v;

    }

};