算法训练营第十三天：二叉树基础

算法训练营第十三天|

• 二叉树理论基础
• 二叉树的递归遍历
  • 卡哥文字以及视频讲解链接
    • 重点
    • c++实现（前序遍历）中，左，右
    • c++实现（中序遍历）左，中，右
    • c++实现（后序遍历）左，右，中
• 二叉树的迭代遍历
  • 卡哥文字以及视频讲解链接
    • 重点
    • c++实现（前序遍历）中，左，右
    • c++实现（中序遍历）左，中，右
    • c++实现（后序遍历）左，右，中
• 二叉树的统一迭代法
  • 卡哥文字以及视频讲解链接
    • 重点
    • c++实现 （前序遍历）使用null表示使用
    • c++实现 (中序遍历）使用null表示使用
    • c++实现 (后序遍历）使用null表示使用
    • c++实现 (中序遍历）使用 pair 携带一个bool来确定元素状态
• 二叉树层序遍历
  • 卡哥文字以及视频讲解链接
    • 重点
    • c++实现
  • 一个重点
• 坚持就是胜利

二叉树理论基础

• 二叉树类型有：满二叉树、完全二叉树、二叉搜索树和平衡二叉搜索树。
• 存储方式有：链式存储（指针）和顺序存储（数组）。
• 遍历方式有：
  1. 深度优先：前中后序遍历（递归，迭代）
  2. 广度优先：层序遍历（迭代）
• 二叉树结点的定义

* Definition for a binary tree node.*structTreeNode{*int val;* TreeNode *left;* TreeNode *right;*TreeNode():val(0),left(nullptr),right(nullptr){}*TreeNode(int x):val(x),left(nullptr),right(nullptr){}*TreeNode(int x, TreeNode *left, TreeNode *right):val(x),left(left),right(right){}*};

二叉树的递归遍历

卡哥文字以及视频讲解链接

重点

• 二叉树的学习引入了递归的大量使用
• 递归三要素：
  1. 确定递归函数的参数和返回值
  2. 确定终止条件
  3. 确定单层递归的逻辑
• 递归开销大，内存占用久

c++实现（前序遍历）中，左，右

classSolution{public: vector<int>preorderTraversal(TreeNode* root){// if(root == nullptr) return {};三处注释搭配使用，起到递归函数中的终止条件作用 vector<int> result;travalTree(root, result);return result;}voidtravalTree(TreeNode* root, vector<int>& result){//这个引用很重要if(root ==nullptr)return;//终止条件 result.push_back(root -> val);//中/*if(root -> left)*/travalTree(root -> left, result);//左孩子/*if(root -> right)*/travalTree(root -> right, result);//右孩子return;}};

c++实现（中序遍历）左，中，右

classSolution{public: std::vector<int>preorderTraversal(TreeNode* root){ std::vector<int> result;traverse(root, result);return result;}private:voidtraverse(TreeNode* node, std::vector<int>& res){if(node ==nullptr)return;//递归终止条件traverse(node->left, res);//左 res.push_back(node->val);//中traverse(node->right, res);//右}};

c++实现（后序遍历）左，右，中

classSolution{public: vector<int>postorderTraversal(TreeNode* root){ vector<int> result;travalTree(root, result);return result;}voidtravalTree(TreeNode* root, vector<int>& result){if(root ==nullptr)return;travalTree(root -> left, result);travalTree(root -> right, result); result.push_back(root -> val);}};

二叉树的迭代遍历

卡哥文字以及视频讲解链接

重点

• 手动实现一遍，按照实现步骤转换成代码，就理解了
• 就是一个栈，放进放出。
• 只用栈，所有的循环判断依靠的是栈本身。弹出顺序和使用顺序一致。
• 中序遍历使用一个栈无法实现，就是因为栈顶节点和要使用节点不一致。循环判断条件依靠的是帮助指定的指针和栈本身。

c++实现（前序遍历）中，左，右

classSolution{public: vector<int>preorderTraversal(TreeNode* root){ stack<TreeNode*> st; vector<int> result;if(root ==nullptr)return result;//检查非空，防止越界 st.push(root);//和while条件搭配while(!st.empty()){ TreeNode* temp = st.top(); st.pop(); result.push_back(temp -> val);//栈的特点，先进后出，所以要先使用就要后放。先放右，再放左if(temp -> right) st.push(temp -> right);if(temp -> left) st.push(temp -> left);}return result;}};

c++实现（中序遍历）左，中，右

一直向左走到底（入栈），遇到空就弹出栈顶（即“回溯”），访问该节点，然后转向其右子树。

classSolution{public: vector<int>inorderTraversal(TreeNode* root){ vector<int> result; stack<TreeNode*> st; TreeNode* cur = root;//这个循环是为了使用curwhile(cur !=NULL||!st.empty()){if(cur !=nullptr){ st.push(cur); cur = cur -> left;//左}else{ cur = st.top(); st.pop(); result.push_back(cur -> val);//中 cur = cur -> right;//右}}return result;}};

• 因为栈放进去之后，所有元素都没有区别，只有栈顶获取，弹出，所以需要另一个指针来确定栈顶的元素是否要使用

c++实现（后序遍历）左，右，中

classSolution{public: vector<int>postorderTraversal(TreeNode* root){ vector<int> result; stack<TreeNode*> st;if(root ==nullptr)return result; st.push(root);while(!st.empty()){ TreeNode* temp = st.top(); st.pop(); result.push_back(temp -> val);//因为要保证使用顺序是先中，所以把左右中看作中右左的逆序。if(temp -> left) st.push(temp -> left);if(temp -> right) st.push(temp -> right);}//整体反转reverse(result.begin(), result.end());return result;}};

二叉树的统一迭代法

卡哥文字以及视频讲解链接

重点

• 两种方法
• 第一种，一个节点可以处理的范围是自己和左右孩子（该节点的根，该节点处理不到）。节点分两部分完成遍历，第一次通过节点来获得左右孩子，第二次看到第一次处理过的标志直接处理本节点。
• 第二种，给一个pair，first表示节点，second表示是否使用过。
• 本质是一种方式，就是让节点分两步进行。没处理过的先处理，处理过的直接用。

c++实现 （前序遍历）使用null表示使用

classSolution{public: vector<int>preorderTraversal(TreeNode* root){ vector<int> result; stack<TreeNode*> st;if(root ==nullptr)return{};//检查非空 st.push(root);//还是和while搭配while(!st.empty()){ TreeNode* temp = st.top();//每次进入首先获取栈顶元素if(temp){ st.pop();//因为是前序，需要弹出重新排一下序if(temp -> right) st.push(temp -> right);if(temp -> left) st.push(temp -> left); st.push(temp); st.push(nullptr);//在要使用元素后加一个 NULL 表示这个节点和周围的父子关系已经实现过了，下一次就是使用}else{//栈顶为空，弹出，获得新栈顶，使用 st.pop(); temp = st.top(); st.pop(); result.push_back(temp -> val);}}return result;}};

c++实现 (中序遍历）使用null表示使用

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

c++实现 (后序遍历）使用null表示使用

classSolution{public: vector<int>postorderTraversal(TreeNode* root){ vector<int> result; stack<TreeNode*> st;if(root ==nullptr)return{}; st.push(root);while(!st.empty()){ TreeNode* temp = st.top();if(temp){//这里不用弹出 st.push(nullptr);if(temp -> right) st.push(temp -> right);if(temp -> left) st.push(temp -> left);}else{ st.pop(); temp = st.top(); st.pop(); result.push_back(temp -> val);}}return result;}};

c++实现 (中序遍历）使用 pair 携带一个bool来确定元素状态

classSolution{public: vector<int>inorderTraversal(TreeNode* root){ vector<int> result; stack<pair<TreeNode*,bool>> st;if(root !=nullptr) st.push(make_pair(root,false));// 多加一个参数，false 为默认值，含义见下文注释while(!st.empty()){auto node = st.top().first;auto visited = st.top().second;//多加一个 visited 参数，使“迭代统一写法”成为一件简单的事 st.pop();if(visited){// visited 为 True，表示该节点和两个儿子位次之前已经安排过了，现在可以收割节点了 result.push_back(node->val);continue;}// visited 当前为 false, 表示初次访问本节点，此次访问的目的是“把自己和两个儿子在栈中安排好位次”。// 中序遍历是'左中右'，右儿子最先入栈，最后出栈。if(node->right) st.push(make_pair(node->right,false));// 把自己加回到栈中，位置居中。// 同时，设置 visited 为 true，表示下次再访问本节点时，允许收割。 st.push(make_pair(node,true));if(node->left) st.push(make_pair(node->left,false));// 左儿子最后入栈，最先出栈}return result;}};

二叉树层序遍历

卡哥文字以及视频讲解链接

重点

• 逐层

c++实现

classSolution{public: vector<vector<int>>levelOrder(TreeNode* root){ queue<TreeNode*> que; vector<vector<int>> result;if(root ==nullptr)return result; que.push(root);while(!que.empty()){int size = que.size(); vector<int> vec;for(int i =0; i < size ; i++){ TreeNode* temp = que.front(); que.pop(); vec.push_back(temp -> val);if(temp -> left) que.push(temp -> left);if(temp -> right) que.push(temp -> right);} result.push_back(vec);}return result;}};

一个重点

• 也是特点吧
• 遍历的时候，如果单一使用栈或者队列，函数体内的循环逻辑围绕的就是栈或队列是否为空
• 如果是中序迭代，遍历需要一个指针来辅助，函数体内的循环逻辑围绕的就是栈是否空以及指针是否为空
• 这样便于记忆二叉树的遍历逻辑

坚持就是胜利

• 第十三天，搞定！

author轩