二叉树
1、二叉树的建立
层序遍历重建二叉树
测试样例：
11
3 9 20 -1 -1 15 7 -1 -1 -1 -1
中序遍历结果：
9 3 15 20 7
#include<iostream> #include<cstdio> using namespace std; int n, num; //定义一棵二叉树 struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {} }; //层序遍历创建二叉树 TreeNode* make(int p[], int u) { if (u > n || p[u] == -1) return nullptr; TreeNode* root = new TreeNode(p[u]); root->left = make(p, u * 2); root->right = make(p, u * 2 + 1); return root; } //中序遍历二叉树 void dfs(TreeNode* root) { if (!root) return; dfs(root->left); cout << root->val << ' '; dfs(root->right); } int main() { cin>>n; int p[n + 1]; for(int i = 1; i <= n; i++) cin>>p[i]; TreeNode* root = make(p, 1); dfs(root); return 0; }
2、前序遍历二叉树
样例：
递归写法
class Solution { public: vector<int> res; vector<int> preorderTraversal(TreeNode* root) { if(!root) return {}; dfs(root); return res; } void dfs(TreeNode* root){ if(!root) return; res.push_back(root->val); dfs(root->left); dfs(root->right); } };
迭代写法
迭代算法的本质是模拟递归，只不过递归使用了系统栈，而在迭代算法中我们使用stack模拟系统栈。
迭代算法中，对于二叉树中的当前节点：
- 将当前节点压入栈中，并记录到答案中。
- 如果当前节点还有左儿子的话，继续将其左儿子压入栈中。
- 重复上述过程，直到最后一个节点没有左儿子为止。
这样，我们就将当前节点和它的左侧子节点全部访问完毕了（相当于我们已经访问了根节点和左子树节点），栈中存放着当前节点和它的全部左侧子节点。接下来我们该要去访问当前节点的右子树了，由于栈是先进后出的，此时栈顶元素的右子节点就是前序遍历的下一个要遍历的节点，因此：
- 取出栈顶元素的右子节点。
- 当前栈顶元素已经访问完毕，我们将其弹出。
- 如果当前栈顶元素的右子节点不为空，我们继续将其当成当前节点，重复对当前节点的处理过程。
class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> stk; while(root || stk.size()){ while(root){ res.push_back(root->val); stk.push(root); root = root->left; } root = stk.top(); stk.pop(); root = root->right; } return res; } };
完整代码
#include<iostream> #include<cstdio> #include<stack> using namespace std; int n, num; //定义一棵二叉树 struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {} }; //层序遍历创建二叉树 TreeNode* make(int p[], int u) { if (u > n || p[u] == -1) return nullptr; TreeNode* root = new TreeNode(p[u]); root->left = make(p, u * 2); root->right = make(p, u * 2 + 1); return root;1 } //迭代前序遍历二叉树 void dfs(TreeNode* root) { stack<TreeNode*> stk; while(root || stk.size()){ while(root){ cout<<root->val<<' '; stk.push(root); root = root->left; } root = stk.top(); stk.pop(); root = root->right; } } int main() { cin>>n; int p[n + 1]; for(int i = 1; i <= n; i++) cin>>p[i]; TreeNode* root = make(p, 1); dfs(root); return 0; }
3、中序遍历二叉树
递归写法
class Solution { public: vector<int> res; vector<int> inorderTraversal(TreeNode* root) { dfs(root); return res; } void dfs(TreeNode * root) { if(!root) return ; dfs(root->left); //左 res.push_back(root->val); //根 dfs(root->right); //右 } };
迭代写法
class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> stk; while(root || stk.size()){ while(root){ stk.push(root); root = root->left; } root = stk.top(); stk.pop(); res.push_back(root->val); root = root->right; } return res; } };
完整代码
#include<iostream> #include<cstdio> #include<stack> using namespace std; int n, num; //定义一棵二叉树 struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {} }; //层序遍历创建二叉树 TreeNode* make(int p[], int u) { if (u > n || p[u] == -1) return nullptr; TreeNode* root = new TreeNode(p[u]); root->left = make(p, u * 2); root->right = make(p, u * 2 + 1); return root; } //迭代中序遍历二叉树 void dfs(TreeNode* root) { stack<TreeNode*> stk; while(root || stk.size()){ while(root){ stk.push(root); root = root->left; } root = stk.top(); stk.pop(); cout<<root->val<<' '; root = root->right; } } int main() { cin>>n; int p[n + 1]; for(int i = 1; i <= n; i++) cin>>p[i]; TreeNode* root = make(p, 1); dfs(root); return 0; }
4、后序遍历二叉树
递归写法
class Solution { public: vector<int>res; vector<int> postorderTraversal(TreeNode* root) { dfs(root); return res; } void dfs(TreeNode* root) { if(root == NULL) return; dfs(root->left); dfs(root->right); res.push_back(root->val); } };
迭代写法
- 前序遍历的顺序：根，左，右
- 可以根据类型前序遍历的思想，遍历出：根，右，左
- 再通过 2 中遍历出来的顺序，通过反转得到后序遍历：左，右，根
class Solution { public: vector<int> postorderTraversal(TreeNode* root) { vector<int> res; stack<TreeNode*> stk; while(root || stk.size()){ while(root){ res.push_back(root->val); stk.push(root); root = root->right; } root = stk.top(); stk.pop(); root = root->left; } reverse(res.begin(), res.end()); return res; } };
完整代码
#include<iostream> #include<cstdio> #include<stack> #include<vector> #include<algorithm> using namespace std; int n, num; //定义一棵二叉树 struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int _val) : val(_val), left(nullptr), right(nullptr) {} }; //层序遍历创建二叉树 TreeNode* make(int p[], int u) { if (u > n || p[u] == -1) return nullptr; TreeNode* root = new TreeNode(p[u]); root->left = make(p, u * 2); root->right = make(p, u * 2 + 1); return root; } //迭代后序遍历二叉树 void dfs(TreeNode* root) { vector<int> res; stack<TreeNode*> stk; while(root || stk.size()){ while(root){ res.push_back(root->val); stk.push(root); root = root->right; } root = stk.top(); stk.pop(); root = root->left; } reverse(res.begin(), res.end()); for(int i = 0; i < res.size(); i++) cout<<res[i]<<' '; } int main() { cin>>n; int p[n + 1]; for(int i = 1; i <= n; i++) cin>>p[i]; TreeNode* root = make(p, 1); dfs(root); return 0; }
5、什么是完全二叉树？
定义：若设二叉树的深度为k，除第k层外，其他各层（1～（k-1）层）的节点数都达到最大值，且第k层所有的节点都连续集中在最左边，这样的树就是完全二叉树。
性质：
- 对于任意一个节点，如果其有左子节点，那么它一定有右子节点。
- 对于任意一个节点，如果其有右子节点，那么它一定有左子节点。
- 最后一层的节点数目小于等于上一层的节点数目的两倍。
- 深度为k的完全二叉树至多有2^k-1个节点。
6、什么是二叉搜索树？
二叉搜索树又称二叉排序树，具有以下性质：
- 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值；
- 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值；
- 它的左右子树也分别为二叉搜索树。
注意：二叉搜索树中序遍历的结果是有序的。
7、什么是平衡二叉树？
定义：平衡二叉树是一种特殊的二叉树，其中每一个节点的左子树和右子树的高度差都不超过1。平衡二叉树的这种性质使得它在查找、插入和删除操作时具有较高的效率，并且能够保证操作的时间复杂度为O(logn)。
性质：
- 每个节点的左子树和右子树的高度差不超过1。
- 在插入或删除节点后，树会自动调整其结构以保持平衡。
- 在查找、插入和删除操作时，时间复杂度都是O(logn)。
- 平衡二叉树的高度较低，通常比普通的二叉搜索树要小。
