龙岗网站seo,建筑设计前景怎么样,一个服务器放多少网站,wordpress默认主题页脚刷题的第十一天#xff0c;希望自己能够不断坚持下去#xff0c;迎来蜕变。#x1f600;#x1f600;#x1f600; 刷题语言#xff1a;C / Python Day11 任务 ● 理论基础 ● 递归遍历 ● 迭代遍历 ● 统一迭代
1 二叉树理论基础
1.1 二叉树的种类
#xff08;1希望自己能够不断坚持下去迎来蜕变。 刷题语言C / Python Day11 任务 ● 理论基础 ● 递归遍历 ● 迭代遍历 ● 统一迭代
1 二叉树理论基础
1.1 二叉树的种类
1满二叉树 深度为 k k k有 2 k − 1 2^k-1 2k−1个节点的二叉树 2完全二叉树 定义在完全二叉树中除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h h h 层 h h h从 1 1 1开始则该层包含 1~ 2 h − 1 2^{h-1} 2h−1个节点 优先级队列其实是一个堆堆就是一棵完全二叉树同时保证父子节点的顺序关系 3二叉搜索树 前面的树没有数值而二叉搜索树是有数值的二叉搜索树是一个有序树 1.若它的左子树不空则左子树上所有结点的值均小于它的根结点的值 2.若它的右子树不空则右子树上所有结点的值均大于它的根结点的值 3.它的左、右子树也分别为二叉排序树 4平衡二叉搜索树 平衡二叉搜索树又被称为AVLAdelson-Velsky and Landis树是一棵空树或它的左右两个子树的高度差的绝对值不超过1并且左右两个子树都是一棵平衡二叉树 C中map、set、multimapmultiset的底层实现都是平衡二叉搜索树所以map、set的增删操作时间时间复杂度是 l o g n logn logn
1.2 二叉树的存储方式
链式存储和顺序存储 顺序存储的元素在内存是连续分布的而链式存储则是通过指针把分布在各个地址的节点串联一起 如果父节点的数组下标是 i i i左孩子就是 i ∗ 2 1 i * 21 i∗21右孩子就是 i ∗ 2 2 i * 22 i∗22 1.3 二叉树的遍历方式
二叉树主要有两种遍历方式
深度优先遍历先往深走遇到叶子节点再往回走。广度优先遍历一层一层的去遍历。
深度优先遍历 前序遍历递归法迭代法中左右中序遍历递归法迭代法左中右后序遍历递归法迭代法左右中 这里前中后其实指的就是中间节点的遍历顺序 前中后序遍历的逻辑其实都是可以借助栈使用递归的方式来实现的 广度优先遍历 层次遍历迭代法 广度优先遍历的实现一般使用队列来实现这也是队列先进先出的特点所决定的因为需要先进先出的结构才能一层一层的来遍历二叉树
这两种遍历是图论中最基本的两种遍历方式
1.4 二叉树的定义
C
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};Python
class TreeNode:def __init__(self, val, left None, right None):self.val valself.left leftself.right right2 递归遍历
递归的三要素
确定递归函数的参数和返回值 确定哪些参数是递归的过程中需要处理的那么就在递归函数里加上这个参数 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型 确定终止条件 运行遇到栈溢出的错误就是没写终止条件或者终止条件写的不对操作系统也是用一个栈的结构来保存每一层递归的信息如果递归没有终止操作系统的内存栈必然就会溢出 确定单层递归的逻辑 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程 前序遍历 1确定递归函数的参数和返回值
void traversal(TreeNode* cur, vectorint vec)2确定终止条件
if (cur NULL) return;3确定单层递归的逻辑 前序遍历是中左右
vec.push_back(cur-val); // 中
traversal(cur-left, vec); // 左
traversal(cur-right, vec);// 右C
class Solution {
public:void traversal(TreeNode* cur, vectorint vec){if (cur NULL) return;vec.push_back(cur-val); // 中traversal(cur-left, vec); // 左traversal(cur-right, vec);// 右}vectorint preorderTraversal(TreeNode* root) {vectorint result;traversal(root, result);return result;}
};Python
class Solution(object):def preorderTraversal(self, root)::type root: TreeNode:rtype: List[int]if not root:return []left self.preorderTraversal(root.left)right self.preorderTraversal(root.right)return [root.val] left right中序遍历 C
class Solution {
public:void traversal(TreeNode* cur, vectorint vec){if (cur NULL) return;traversal(cur-left, vec); // 左vec.push_back(cur-val); // 中traversal(cur-right, vec);// 右}vectorint inorderTraversal(TreeNode* root) {vectorint result;traversal(root, result);return result;}
};Python
class Solution(object):def inorderTraversal(self, root)::type root: TreeNode:rtype: List[int]if not root:return []left self.inorderTraversal(root.left)right self.inorderTraversal(root.right)return left [root.val] right后序遍历 C
class Solution {
public:void traversal(TreeNode* cur, vectorint vec){if (cur NULL) return;traversal(cur-left, vec); // 左traversal(cur-right, vec); // 右vec.push_back(cur-val); // 中}vectorint postorderTraversal(TreeNode* root) {vectorint result;traversal(root, result);return result;}
};Python
class Solution(object):def postorderTraversal(self, root)::type root: TreeNode:rtype: List[int]if not root:return []left self.postorderTraversal(root.left)right self.postorderTraversal(root.right)return left right [root.val]3 迭代遍历
递归的实现就是每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中然后递归返回的时候从栈顶弹出上一次递归的各项参数所以这就是递归为什么可以返回上一层位置的原因 用栈也可以实现二叉树的前后中序遍历
3.1 前序遍历迭代法
前序遍历是中左右每次先处理的是中间节点那么先将根节点放入栈中然后将右孩子加入栈再加入左孩子。 出栈的时候才是中左右的顺序 C
class Solution {
public:vectorint preorderTraversal(TreeNode* root) {stackTreeNode* st;vectorint 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;}
};目前的前序遍历的逻辑无法直接应用到中序遍历上
3.2 后序遍历迭代法 C
class Solution {
public:vectorint postorderTraversal(TreeNode* root) {stackTreeNode* st;vectorint 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;}
};3.3 中序遍历迭代法
中序遍历是左中右先访问的是二叉树顶部的节点然后一层一层向下访问直到到达树左面的最底部再开始处理节点也就是在把节点的数值放进result数组中这就造成了处理顺序和访问顺序是不一致的。 在使用迭代法写中序遍历就需要借用指针的遍历来帮助访问节点栈则用来处理节点上的元素
class Solution {
public:vectorint inorderTraversal(TreeNode* root) {vectorint result;TreeNode* cur root;stackTreeNode* st;while (cur ! NULL || !st.empty()){if (cur ! NULL)// 指针来访问节点访问到最底层{st.push(cur);// 将访问的节点放进栈cur cur-left;// 左}else{cur st.top();// 从栈里弹出的数据就是要处理的数据st.pop();result.push_back(cur-val);// 中cur cur-right;// 右}}return result;}
};鼓励坚持十二天的自己
