【第一部分】01Leetcode刷题

一、二叉树的中序遍历

题目：94. 二叉树的中序遍历、94. Binary Tree Inorder Traversal

解法一：

 1 class Solution {
 2 public:
 3     vector<int> inorderTraversal(TreeNode* root) 
 4     {
 5         if(!root) {};
 6         vector<int> res;
 7         stack<TreeNode *> st;
 8         while(root || !st.empty())
 9         {
10             while(root)
11             {
12                 st.push(root);
13                 root = root->left;
14             }
15             root = st.top();
16             st.pop();
17             res.push_back(root->val);
18             root = root->right;
19         }
20         return res;       
21     }
22 };

解法二：

 1 class Solution {    
 2 public:
 3     vector<int> res;
 4     vector<int> inorderTraversal(TreeNode* root) 
 5     {
 6         if(!root) return {};
 7         inorderTraversal(root->left);
 8         res.push_back(root->val);
 9         inorderTraversal(root->right);
10         return res;     
11     }
12 };

二、二叉树的前序遍历

题目：144. 二叉树的前序遍历、144. Binary Tree Preorder Traversal

解法一：

 1 class Solution {
 2 public:
 3     vector<int> preorderTraversal(TreeNode* root) 
 4     {
 5         if(!root) return {};
 6         vector<int> res;
 7         stack<TreeNode *> st;
 8         st.push(root);
 9         while(!st.empty())
10         {
11             root = st.top();
12             st.pop();
13             res.push_back(root->val);
14             if(root->right) st.push(root->right);
15             if(root->left) st.push(root->left);
16         }
17         return res;     
18     }
19 };

解法二：

 1 class Solution {
 2 public:
 3     vector<int> res;
 4     vector<int> preorderTraversal(TreeNode* root) 
 5     {
 6         if(!root) return {};
 7         res.push_back(root->val);
 8         preorderTraversal(root->left);
 9         preorderTraversal(root->right);
10         return res;      
11     }
12 };

三、两个数组的交集 II

题目：350. 两个数组的交集 II 、350. Intersection of Two Arrays II

解法一：

 1 class Solution {
 2 public:
 3     vector<int> intersect(vector<int>& nums1, vector<int>& nums2) 
 4     {
 5         unordered_map<int, int> mp;
 6         vector<int> res;
 7         for(auto c: nums1) ++mp[c];
 8         for(auto c: nums2)
 9             if(mp[c]--> 0)
10                 res.push_back(c);
11         return res;
12     }
13 };