二叉树中序遍历

中序:左-根-右

C++迭代

一个模板写法：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {         
        vector<int> ans;  
        stack<TreeNode*> node;
        if(!root) return ans;
        node.push(root);
        while(!node.empty()){
            TreeNode* cur = node.top();
            node.pop();
            if(cur != nullptr){
                if(cur->right) node.push(cur->right);
                node.push(cur);
                node.push(nullptr);       
                ###右-上-nullptr-左###       
                if(cur->left) node.push(cur->left);
            }
            else{
                ans.push_back(node.top()->val);
                node.pop();
            }
        }
        return ans;
    }
};

自己想的
1.先入栈再访问
2.左臂入栈法

class Solution {
public:
    vector<int> ans;
    #stack<TreeNode*> node 也可
    vector<TreeNode*> node;

    vector<int> inorderTraversal(TreeNode* root) {           
        if(root == NULL) return ans;
        find(root);

        while(!node.empty()){
            TreeNode* cur = node.back();
            node.pop_back();
            ans.push_back(cur->val);
            if(cur->right != NULL) find(cur->right); 
        }
        return ans;
    }
    void find(TreeNode* root){
        while(root != NULL){
            node.push_back(root);
            root = root->left;
        }
    }
};

C++递归

先递归左子树，然后添加根节点，再递归右子树

class Solution {
public:
    vector<int> ans;

    vector<int> inorderTraversal(TreeNode* root) {           
        if(root){
            inorderTraversal(root->left);
            ans.push_back(root->val);
            inorderTraversal(root->right);
        }
        return ans;
    }
};