代码随想录打卡第十三天

代码随想录–二叉树部分

day13 二叉树第一天

文章目录

代码随想录--二叉树部分
二叉树基础知识
一、力扣144--二叉树的前序遍历（递归）
二、力扣145--二叉树的后序遍历（递归）
三、力扣94--二叉树的中序遍历（递归）
四、力扣144--二叉树的前序遍历（迭代）
五、力扣145--二叉树的后序遍历（迭代）
六、力扣94--二叉树的中序遍历（迭代）
七、力扣144--二叉树的前序遍历（统一迭代）
八、力扣145--二叉树的后序遍历（统一迭代）
九、力扣94--二叉树的中序遍历（统一迭代）
十、力扣102--二叉树的层序遍历

二叉树基础知识

代码随想录知识链接：代码随想录

几个核心概念
满二叉树：结点的度只有0和2，且度为0的节点在同一层
完全二叉树：除了最后一层，其他层都满节点，最后一层的节点从左往右排
二叉搜索树：带值的二叉树，左节点<根节点<右节点
平衡二叉树：空树或左右子树高度差不大于1

遍历方法：
今天的题目都是遍历，在题目中介绍

一、力扣144–二叉树的前序遍历（递归）

代码随想录知识链接：代码随想录

给你二叉树的根节点 root ，返回它节点值的前序遍历。

前序遍历意思就是根节点->左节点->右节点这种顺序遍历下去，先用递归方法

定义一个子函数，接受一个根节点，如果根节点为null就return，否则先递归其左节点，再递归其右节点

代码如下：

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

二、力扣145–二叉树的后序遍历（递归）

代码随想录知识链接：代码随想录

给你一棵二叉树的根节点 root ，返回其节点值的后序遍历。

后序遍历就是从子节点先遍历，左节点->右节点->根节点，调换一下子函数的顺序就行

代码如下：

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

三、力扣94–二叉树的中序遍历（递归）

代码随想录知识链接：代码随想录

给定一个二叉树的根节点 root ，返回它的中序遍历。

中序的顺序是左节点->根节点->右节点

代码如下：

class Solution {
public:void trans(TreeNode* curr, vector<int> & result){if(curr == nullptr) return;trans(curr->left, result);result.push_back(curr->val);trans(curr->right, result);     }vector<int> inorderTraversal(TreeNode* root) {vector<int> result;trans(root, result);return result;}
};

四、力扣144–二叉树的前序遍历（迭代）

代码随想录知识链接：代码随想录

这次用迭代方法来遍历。递归的实现本身是每次递归调用都把函数压入调用栈中，等递归结束时，就从栈顶弹出上次递归的参数，迭代法也就是模拟这个过程。

前序是中左右，但是因为栈是先入后出，所以实际上压栈的顺序应该是右左中

代码如下：

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

五、力扣145–二叉树的后序遍历（迭代）

代码随想录知识链接：代码随想录

同样的，用遍历+栈模拟递归过程，先序是中左右，后序是左右中，也就是中右左的逆序，而中右左是很好调整的

代码如下：

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;if(root == nullptr) return result;st.push(root);while(!st.empty()){TreeNode * curr = st.top();result.push_back(curr->val);st.pop();if(curr->left)st.push(curr->left);if(curr->right)st.push(curr->right); // switch order}reverse(result.begin(), result.end()); // reverse the resultreturn result;}
};

六、力扣94–二叉树的中序遍历（迭代）

代码随想录知识链接：代码随想录

中序遍历不管怎么调整，都没法把根节点放在第一位处理，它只能在中间，所以代码没法像前后序那么简单

所以这里栈就可以用来存指针，遍历到底部后，再出栈处理数字
请添加图片描述

代码如下：

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode *> st;TreeNode * curr = root;while(curr != nullptr || !st.empty()){if(curr != nullptr){st.push(curr);curr = curr->left;}else{curr = st.top();st.pop();result.push_back(curr->val);curr = curr->right;}}return result;}
};

七、力扣144–二叉树的前序遍历（统一迭代）

代码随想录知识链接：代码随想录

迭代法明显没有递归法那样漂亮，无法做到三种顺序改一点就能用，所以对迭代法改进，使其更漂亮更易用

其实相当于都写成中序遍历的样子，但是在遍历过未处理的节点入栈后，增加一个NULL指针也入栈，来表示该节点可以输出了

这样不同的遍历顺序只需要改入栈顺序就行，这样就和递归法一样了

代码如下：

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

八、力扣145–二叉树的后序遍历（统一迭代）

代码随想录知识链接：代码随想录

前序是中左右，入栈顺序是右左中，那么后序是左右中，则入栈顺序是中右左

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;if (root != NULL) st.push(root);while (!st.empty()) {TreeNode* node = st.top();if (node != NULL) {st.pop();st.push(node);                          st.push(NULL);if (node->right) st.push(node->right);  if (node->left) st.push(node->left);    } else {st.pop();node = st.top();st.pop();result.push_back(node->val);}}return result;}
};

九、力扣94–二叉树的中序遍历（统一迭代）

代码随想录知识链接：代码随想录

中序输出是左中右，那入栈顺序就是右中左

代码如下：

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

十、力扣102–二叉树的层序遍历

代码随想录知识链接：代码随想录

前中后序遍历都是深度优先遍历，层序遍历就是广度优先了

用队列实现，每次将出队元素的子节点入队，直到队空即可

代码如下：

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> result;queue<TreeNode *> que;if(root != nullptr) que.push(root);{while(!que.empty()){vector<int> temp;int length = que.size();for(int i = 0;i < length; i++) // Use all nodes in this while loop{TreeNode * curr = que.front();que.pop();if(curr->left != nullptr) que.push(curr->left);if(curr->right != nullptr) que.push(curr->right);temp.push_back(curr->val);}result.push_back(temp);}}return result;}
};