二叉树专题 阳光穿透心脏的1/2处 2022-12-28 08:18 120阅读 0赞 ## 二叉树的定义 ## struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; * 满二叉树:只有度为0的结点和度为2的结点,并且度为0的结点在同一层上,深度为k,有2^k-1个节点。 * 完全二叉树:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。 * 二叉搜索树:是一棵有序树。 * 若其左子树不空,则左子树上所有节点的值均小于它的根节点的值 * 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值 * 它的左右子树也分别是二叉排序树 * 平衡二叉搜索树 * 它是一棵空树或它的左右两个子树的高度差绝对值不超过1 * 且左右两个子树都是一棵平衡二叉树 * C++中map、set、multimap,multiset的底层实现都是平衡二叉搜索树,所以map、set的增删操作时间时间复杂度是logn;而unordered\_map、unordered\_set底层实现是哈希表。 ## 二叉树的存储方式 ## * 链式存储:指针,散落的结点 * 顺序存储:数组,内存连续分布 * 如果父节点的数组下表是i,那么它的左孩子就是i \* 2 + 1,右孩子就是 i \* 2 + 2。 ## 二叉树的遍历方式 ## * 深度优先遍历【栈】 * 前序遍历(递归法,迭代法) * 中序遍历(递归法,迭代法) * 后序遍历(递归法,迭代法) * 广度优先遍历【队列】 * 层次遍历(迭代法) ## 递归遍历二叉树的步骤 ## **前序遍历** 1. 确定递归函数的参数和返回值 void traversal(TreeNode* cur, vector<int>& vec) 1. 确定终止条件 if (cur == NULL) return; 1. 确定单层递归的逻辑 vec.push_back(cur->val); // 根 traversal(cur->left, vec); // 左 traversal(cur->right, vec); // 右 **前序遍历(递归)**: class Solution { public: void traversal(TreeNode* cur, vector<int>& vec) { if (cur == NULL) return; vec.push_back(cur->val); // 根 traversal(cur->left, vec); // 左 traversal(cur->right, vec); // 右 } vector<int> preorderTraversal(TreeNode* root) { vector<int> result; traversal(root, result); return result; } }; **前序遍历(栈实现):** class Solution { public: vector<int> preorderTraversal(TreeNode* root) { stack<TreeNode*> st; vector<int> result; st.push(root); while (!st.empty()) { TreeNode* node = st.top(); // 中 st.pop(); if (node != NULL) result.push_back(node->val); else continue; st.push(node->right); // 右 st.push(node->left); // 左 } return result; } }; **中序遍历(递归)** void traversal(TreeNode* cur, vector<int>& vec) { if (cur == NULL) return; traversal(cur->left, vec); // 左 vec.push_back(cur->val); // 根 traversal(cur->right, vec); // 右 } **中序遍历(栈)** 在使用迭代法写中序遍历,就需要借用指针的遍历来帮助访问节点,栈则用来处理节点上的元素 class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> result; stack<TreeNode*> st; TreeNode* cur = root; while (cur != NULL || !st.empty()) { if (cur != NULL) { // 指针来访问节点,访问到最底层 st.push(cur); // 讲访问的节点放进栈 cur = cur->left; // 左 } else { cur = st.top(); // 从栈里弹出的数据,就是要处理的数据(放进result数组里的数据) st.pop(); result.push_back(cur->val); // 中 cur = cur->right; // 右 } } return result; } }; **后序遍历(递归)** void traversal(TreeNode* cur, vector<int>& vec) { if (cur == NULL) return; traversal(cur->left, vec); // 左 traversal(cur->right, vec); // 右 vec.push_back(cur->val); // 根 } **后序遍历(栈)** 后序遍历只需要前序遍历的代码稍作修改就可以了。 class Solution { public: vector<int> postorderTraversal(TreeNode* root) { stack<TreeNode*> st; vector<int> result; st.push(root); while (!st.empty()) { TreeNode* node = st.top(); st.pop(); if (node != NULL) result.push_back(node->val); else continue; st.push(node->left); // 相对于前序遍历,这更改一下入栈顺序 st.push(node->right); } reverse(result.begin(), result.end()); // 将结果反转之后就是左右中的顺序了 return result; } }; **层序遍历(广度优先遍历)** \--利用队列实现 class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { queue<TreeNode*> que; if (root != NULL) que.push(root); vector<vector<int>> result; while (!que.empty()) { int size = que.size(); vector<int> vec; // 这里一定要使用固定大小size,不要使用que.size(),因为que.size是不断变化的 for (int i = 0; i < size; i++) { 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); } result.push_back(vec); } return result; } }; [二叉树:层序遍历登场][Link 1] 里面的例题敲敲会。 [Link 1]: https://mp.weixin.qq.com/s?__biz=MzUxNjY5NTYxNA==&mid=2247484713&idx=1&sn=2072608d432def7457fdfa27b73d8193&scene=21#wechat_redirect
相关 Day30——二叉树专题 文章目录 22.验证二叉搜索树 23.二叉搜索树的最小绝对差 24.二叉搜索树中的插入 谁借莪1个温暖的怀抱¢/ 2024年04月01日 15:23/ 0 赞/ 63 阅读
相关 二叉树专题 二叉树的定义 struct TreeNode { int val; TreeNode left; TreeNod 阳光穿透心脏的1/2处/ 2022年12月28日 08:18/ 0 赞/ 121 阅读
相关 LeetCode 二叉树专题 这是整理的LeetCode上的二叉树专题,按照codeTop上的频率顺序从高到低进行整理。 DFS与非递归写法 二叉树深度优先遍历有三种: 前序:根左右 末蓝、/ 2022年10月17日 01:52/ 0 赞/ 208 阅读
相关 二叉树专题 Tree Summing LISP was one of the earliest high-level programming languages and, with FORTRAN, is one 小灰灰/ 2022年06月13日 10:16/ 0 赞/ 177 阅读
还没有评论,来说两句吧...