hot100---day3

二叉树复习+hot100专题

144. 二叉树的前序遍历 - 力扣（LeetCode）

递归法的前中后序遍历，格式比较一致；

class Solution {
public:vector<int>& traversal(TreeNode* root, vector<int>& ans){if(root==nullptr) return ans;TreeNode* cur =root;ans.push_back(cur->val);traversal(cur->left, ans);traversal(cur->right, ans);return ans;}vector<int> preorderTraversal(TreeNode* root) {vector<int> ans;traversal(root, ans);return ans;}
};

94. 二叉树的中序遍历 - 力扣（LeetCode）

中序遍历；左中右；

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

145. 二叉树的后序遍历 - 力扣（LeetCode）

class Solution {
public:void traversal(TreeNode* node, vector<int>& ans){if(node==nullptr) return;traversal(node->left, ans);traversal(node->right, ans);ans.push_back(node->val);}vector<int> postorderTraversal(TreeNode* root) {vector<int> ans;traversal(root, ans);return ans;}
};

递归法：

前序遍历；

思路：利用数据结构栈来实现，前序，中左右，所以碰到的栈顶元素就需要push_back到数组中去；然后对于左右节点，是右节点先进入，然后左节点，这样弹出的时候才是左节点先弹出，然后右节点弹出；

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> ans;if(root==nullptr) return ans;stack<TreeNode*> st;st.push(root);while(!st.empty()){auto tmp = st.top();st.pop();ans.push_back(tmp->val);if(tmp->right) st.push(tmp->right);if(tmp->left) st.push(tmp->left);}return ans;}
};