迭代

1 /** 2  * Definition for a binary tree node. 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     vector
     
       inorderTraversal(TreeNode* root) {13        vector
      
        ans;14         if(!root) return ans;15         stack
       
         nodeStack;16         while(root) 17         {18             nodeStack.push(root);19             root = root->left;20         }21         while(!nodeStack.empty()) {22             TreeNode* node = nodeStack.top();23             ans.push_back(node->val);24             nodeStack.pop();25             if(node = node->right) {26                 while(node) {27                     nodeStack.push(node);28                     node = node->left;29                 } 30             }31         }32 33         return ans;34     }35 };
       
      
     

优化：

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

 

递归：

1 class Solution { 2 public: 3      void process(TreeNode* root,vector
     
       &ans) 4     { 5        6         if(root->left) process(root->left,ans); 7           ans.push_back(root->val); 8         if(root->right) process(root->right,ans); 9     }10 11     vector
      
        inorderTraversal(TreeNode* root) {12         vector
       
         ans;13         if(root)14             process(root,ans);15         return ans;16     }17 };