立志重刷代码随想录60天冲冲冲!!——第十三天
144. 二叉树的前序遍历
前序:中左右
递归
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: // 确定传入参数、返回值 void traversal (TreeNode* curr, vector<int>& vec) { // 确定终止条件 if (curr == NULL) return; // 确定递归逻辑 vec.push_back(curr->val); traversal(curr->left, vec); traversal(curr->right, vec); } vector<int> preorderTraversal(TreeNode* root) { vector<int> res; traversal(root, res); return res; } };
(迭代)
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<int> preorderTraversal(TreeNode* root) { // 栈存放结点 stack<TreeNode*> st; vector<int> res; if (root == nullptr) return res; st.push(root); while (!st.empty()) { TreeNode* node = st.top(); st.pop(); res.push_back(node->val); // 前序:中左右。但是因为是栈,所以先放右边,后放左边 if (node->right) st.push(node->right); if (node->left) st.push(node->left); } return res; } };
145. 二叉树的后序遍历
前序:左右中
递归
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: void Traversal (TreeNode* curr, vector<int>& vec) { if (curr == nullptr) return; Traversal(curr->left, vec); Traversal(curr->right, vec); vec.push_back(curr->val); } vector<int> postorderTraversal(TreeNode* root) { vector<int> res; Traversal(root, res); return res; } };
迭代
class Solution { public: vector<int> postorderTraversal(TreeNode* root) { stack<TreeNode*> st; vector<int> res; if (root == nullptr) return res; st.push(root); while (!st.empty()) { TreeNode* node = st.top(); st.pop(); res.push_back(node->val); // 后序:左右中。先左后右, if (node->left) st.push(node->left); if (node->right) st.push(node->right); } // 再翻转! reverse(res.begin(), res.end()); return res; } };
94. 二叉树的中序遍历
递归
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: void Traversal (TreeNode* curr, vector<int>& vec) { if (curr == nullptr) return; Traversal(curr->left, vec); vec.push_back(curr->val); Traversal(curr->right, vec); } vector<int> inorderTraversal(TreeNode* root) { vector<int> res; Traversal(root, res); return res; } };
102. 二叉树的层序遍历
重点记!!!!!!
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { queue<TreeNode*> que; vector<vector<int>> results; if (root != nullptr) que.push(root); while (!que.empty()) { int size = que.size(); vector<int> vec; while (size--) { TreeNode* node = que.front(); que.pop(); vec.push_back(node->val); if (node->left) que.push(node->left); if (node->right) que.push(node->right); } results.push_back(vec); } return results; } };
107. 二叉树的层序遍历 II
在最后反转数组就行
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<vector<int>> levelOrderBottom(TreeNode* root) { queue<TreeNode*> que; vector<vector<int>> results; if (root != nullptr) que.push(root); while (!que.empty()) { int size = que.size(); vector<int> vec; while (size--) { TreeNode* node = que.front(); que.pop(); vec.push_back(node->val); if (node->left) que.push(node->left); if (node->right) que.push(node->right); } results.push_back(vec); } reverse(results.begin(), results.end()); return results; } };