二叉树的中序遍历---leetcode 94题

解法1：递归法 

class Solution {
public:
    void traversal(TreeNode* cur, vector& v){
        if(cur == NULL) return;
        traversal(cur->left, v);
        v.push_back(cur->val);
        traversal(cur->right, v);
    }
    vector inorderTraversal(TreeNode* root) {
        vector v;
        traversal(root, v);
        return v;
    }
};

解法2：迭代法 

class Solution {
public:
    vector inorderTraversal(TreeNode* root) {
        vector v;
        stack st;
        TreeNode* cur = root;
        while(cur != NULL || !st.empty()){
            if(cur != NULL){
                st.push(cur);
                cur = cur->left;
            }else{
                cur = st.top();
                st.pop();
                v.push_back(cur->val);
                cur = cur->right;
            }
        }
        return v;
    }
};

解法3 

class Solution {
public:
    vector inorderTraversal(TreeNode* root) {
        vector result;
        stack st;
        if(root != NULL) st.push(root);
        while(!st.empty()) {
            TreeNode* node = st.top();
            if(node != NULL) {
                st.pop();
                if(node->right) st.push(node->right);

                st.push(node);
                st.push(NULL);

                if(node->left) st.push(node->left);
            }else{
                st.pop();
                node = st.top();
                st.pop();
                result.push_back(node->val);
            }
        }
        return result;
    }
};