二叉树是指度为 2 的树。它是一种最简单却又最重要的树在计算机领域中被广泛应用。二叉树的递归定义如下二叉树是一棵空树或者一棵由一个根节点和两棵互不相交的分别称为根节点的左子树和右子树所组成的非空树左子树和右子树同样都是一棵二叉树。在二叉树中每个节点的左子树的根节点被称为左孩子节点右子树被称为右孩子节点。二叉树的结构就决定了二叉树相关的算法与递归有着紧密的联系。二叉树通常使用如下数据结构来表示data 表示二叉树节点的数值left_child 表示节点的左孩子节点right_child 表示节点的右孩子节点。struct node { int data; struct node *left_child; struct node *right_child; }从二叉树的定义来看有以下两点;(1) 二叉树可以是一棵空树(2) 二叉树的左子树和右子树不一定存在可能同时不存在可能同时存在也可能左子树和右子树只存在一个为什么要有二叉树 ?在我们使用数据结构来存储数据的时候最常见的两个使用场景是查找和插入。查找就是从数据结构中找到我们想要的值插入是将一个新值插入到数据结构正确的位置。数据结构是用来存储数据的更大维度的数据存储就是文件系统和数据库。在数据结构中最常用的两个基础的数据结构是数组和链表数组和链表的区别可以从如下 3 个方面来看① 插入元素。数组的插入效率比链表低因为数组插入的时候插入位置后边的元素都要向后移动而向链表中插入元素的时候只需要改变节点的指向就可以。前者的时间复杂度是 O(n) 的后者的时间复杂度是 O(1) 的。② 读取元素。读取数组中的第几个元素的时候使用数组的下标直接读取就可以而读取链表中的第几个元素的时候需要对链表进行遍历。前者的时间复杂度是 O(1) 的后者的时间复杂度是 O(n) 的。③ cache。数组用一块连续的内存来维护链表中每个节点的地址并不连续。从 cpu cache LRU 算法的角度来看的话数组中的元素离的更近所以访问性能会更高。从数组和链表的对比来看没有哪种数据结构是具备所有的优点的。在实际工程中如果对读取和插入的性能要求都很高那么可以同时使用数据和链表来存储数据典型的用空间换时间。二叉树有 3 个重要的变种分别是二叉排序树、二叉平衡树、红黑树。1二叉排序树二叉排序数是一棵特殊的二叉树在一般的二叉树中区分左子树和右子树但结点的值是无序的。在二叉排序树中不仅区分左子树和右子树而且整个树的节点是有序的。二叉排序树又称二叉搜索树它或者是一棵空树或者是一棵非空二叉树具备如下 3 个特点① 如果左子树非空那么左子树上所有节点的值小于根节点的值② 如果右子树非空那么右子树上所有节点的值大于根节点的值如果允许节点的值相等那么大于等于③ 左、右子树本身又各是一棵二叉排序树从分析可以得出在查找的性能上二叉排序树的时间复杂度是 O(logn)相对于链表的 O(n)是有优化的。但是二叉排序树最差的情况是每个节点都只包含一个子节点这种情况下的时间复杂度就成为了 O(n)所以在二叉排序树的基础上出现了二叉平衡树。2二叉平衡树二叉平衡树首先是一颗二叉排序树在此基础上又增加了一个条件即每个节点的左子树和右子树的高度之差不大于 1。有了这个限制之后查找的时间复杂度就不会出现 O(n) 的情况。但是当向平衡树中插入元素的时候为了保证插入之后二叉树还能满足平衡树的要求需要进行旋转操作。对于频繁插入删除的场景旋转操作过于频繁反而会增加时间的消耗。所以出现了红黑树红黑树在查找和插入操作之间取得了平衡(这样的结论只有专门研究红黑树算法的专业人员才能了解在很多文章和书籍中也是这么说的本人不才只能死记硬背这样的结论)。3红黑树红黑树的前提也是一颗二叉排序在此基础上增加了以下 5 个条件① 红黑树中的节点要么是黑色要么是红色② 红黑树的根节点是黑色③ 红黑树中红色节点不能连续也就是说一个红色节点的父节点和子点都不能是红色④ 从根节点开始到叶子节点每条路径上的黑色节点个数相等⑤ 叶子节点是黑色在红黑树中的叶子结点不是真实存在的叶子结点在下图中用矩形来表示在工程应用中本人还没见过使用平衡树的场景只见过使用红黑树的场景。① 在 linux 内核中维护 struct task_struct 使用了红黑树维护 tcp 接收侧的乱序队列使用了红黑树epoll 中维护监听的 fd也是用了红黑树② 在 cjava 内置的 map 数据结构中使用了红黑树本文只记录二叉树的基本算法不涉及二叉排序树二叉平衡树红黑树相关的算法。1 二叉树遍历二叉树的遍历有 4 中算法前序遍历中序遍历后序遍历以及层序遍历。前 3 种遍历算法中的前、中、后说的是根节点的位置前序遍历的顺序是根节点左子节点右子节点中序遍历的顺序是左子节点根节点右子节点后序遍历的顺序是左子节点右子节点根节点。不管哪种遍历左子节点都在右子节点之前遍历。如果了解图的遍历算法可以知道图的遍历算法包括两种深度优先遍历和广度优先遍历。二叉树的遍历方法中前 3 种类似于图中的深度优先遍历层序遍历类似于广度优先遍历。二叉树跟递归算法联系比较紧密递归算法有两点组成一个是递归退出条件一个是递归计算逻辑也可以称为递归体这一点和循环是有点相似的循环也要有循环停止条件和循环处理逻辑。每种算法的对象都是围绕着一个数据结构都需要有一个驱动力这个驱动力往往就是对数据结构中的元素进行遍历对于数组来说往往就是沿着数组下标进行遍历对于链表来说往往就是从 head 开始沿着 next 向下遍历对于二叉树来说就是沿着 left child 和 right child 进行遍历。对数据进行遍历是算法的基础。算法就是研究怎么处理数据。递归算法不太适合从一开始沿着算法逐渐向下思考使用递归算法的时候我们可以使用一个最简单的场景来理解从简单场景开始。比如对于二叉树来说我们以只有 3 个节点(一个 root一个 left child一个 right child)的二叉树来思考和理解。1.1 前序遍历力扣. - 力扣LeetCode/** * Definition for a binary tree node. * struct TreeNode { * 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) {} * }; */ class Solution { public: vectorint preorderTraversal(TreeNode* root) { if (root nullptr) { return ret; } preScan(root); return ret; } void preScan(TreeNode *root) { ret.push_back(root-val); if (root-left) { preScan(root-left); } if (root-right) { preScan(root-right); } } private: vectorint ret; };1.2 中序遍历力扣. - 力扣LeetCode/** * Definition for a binary tree node. * struct TreeNode { * 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) {} * }; */ class Solution { public: vectorint inorderTraversal(TreeNode* root) { if (root nullptr) { return ret; } midScan(root); return ret; } void midScan(TreeNode *root) { if (root-left) { midScan(root-left); } ret.push_back(root-val); if (root-right) { midScan(root-right); } } private: vectorint ret; };1.3 后续遍历力扣. - 力扣LeetCode/** * Definition for a binary tree node. * struct TreeNode { * 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) {} * }; */ class Solution { public: vectorint postorderTraversal(TreeNode* root) { if (root nullptr) { return ret; } postScan(root); return ret; } void postScan(TreeNode *root) { if (root-left) { postScan(root-left); } if (root-right) { postScan(root-right); } ret.push_back(root-val); } private: vectorint ret; };1.4 层序遍历力扣. - 力扣LeetCode/** * Definition for a binary tree node. * struct TreeNode { * 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) {} * }; */ class Solution { public: vectorvectorint levelOrder(TreeNode* root) { std::queueTreeNode * q; std::vectorvectorint ret; if (root nullptr) { return ret; } q.push(root); while (!q.empty()) { // 用来保存二叉树一层的数据 // 如果只是遍历不用保存数据的话那么是用不着这个数据结构的 vectorint line; int q_size q.size(); for (int i 0; i q_size; i) { TreeNode *node q.front(); q.pop(); line.push_back(node-val); if (node-left) { q.push(node-left); } if (node-right) { q.push(node-right); } } ret.push_back(line); } return ret; } };2 二叉树遍历的应用2.1 求二叉树高度力扣. - 力扣LeetCode求二叉树的高度也是使用递归算法。有两种算法1求出左子树和右子树的高度然后两者的较大值加 1 就是二叉树的高度。通过返回值计算depth。2使用动态规划每一次递归计算的时候相当于向下增加了一层在递归函数的形参中实时维护已经遍历的二叉树的高度二叉树遍历完之后最大值保存的就是二叉树的高度。通过入参计算depth。2.1.1 左子树和右子树较大值int maxDepth(struct TreeNode* root) { if (root NULL) { return 0; } int left_height 0; int right_height 0; if (root-left) { left_height maxDepth(root-left); } if (root-right) { right_height maxDepth(root-right); } if (left_height right_height) { return 1 left_height; } else { return 1 right_height; } }2.1.2 动态规划class Solution { public: int maxDepth(TreeNode* root) { maxDepthHelper(root, 0); return max_depth_; } void maxDepthHelper(TreeNode *root, int depth) { if (root nullptr) { return; } depth; if (depth max_depth_) { max_depth_ depth; } if (root-left) { maxDepthHelper(root-left, depth); } if (root-right) { maxDepthHelper(root-right, depth); } } private: int max_depth_ 0; };2.2 求二叉树宽度层序遍历。二叉树的宽度有两种定义一种是每一层的节点个数节点个数最大者视为二叉树的宽度一种是把二叉树每一层的节点最左边节点和最右边节点之间的节点不全视为这一层的宽度。两个题目均是使用层序遍历后者相对于前者需要维护节点的序号通过序号计算宽度。节点个数作为二叉树的宽度#include iostream #include queue using namespace std; struct TreeNode { int val; TreeNode *left, *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; int getWidth(TreeNode* root) { if (!root) return 0; queueTreeNode* q; q.push(root); int maxWidth 0; while (!q.empty()) { int levelSize q.size(); maxWidth max(maxWidth, levelSize); for (int i 0; i levelSize; i) { TreeNode* node q.front(); q.pop(); if (node-left) q.push(node-left); if (node-right) q.push(node-right); } } return maxWidth; }严格二叉树宽度662. 二叉树最大宽度 - 力扣LeetCode/** * Definition for a binary tree node. * struct TreeNode { * 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) {} * }; */ class Solution { public: int widthOfBinaryTree(TreeNode* root) { if (!root) { return 0; } std::queuestd::pairTreeNode *, unsigned long long q; q.push({root, 0}); int ret 0; while (!q.empty()) { int levelSize q.size(); unsigned long long left 0; unsigned long long right 0; for (int i 0; i levelSize; i) { std::pairTreeNode *, unsigned long long node q.front(); q.pop(); if (node.first-left) { q.push({node.first-left, 2 * node.second 1}); } if (node.first-right) { q.push({node.first-right, 2 * node.second 2}); } if (i 0) { left node.second; } if (i levelSize - 1) { right node.second; } } if (right - left 1 ret) { ret right - left 1; } } return ret; } };2.3 二叉树路径力扣. - 力扣LeetCode/** * Definition for a binary tree node. * struct TreeNode { * 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) {} * }; */ class Solution { public: vectorstring binaryTreePaths(TreeNode* root) { if (!root) { return ret; } tmp_data_path.push_back(root-val); if (root-left nullptr root-right nullptr) { string str_path makePath(); ret.push_back(str_path); return ret; } if (root-left) { binaryTreePaths(root-left); tmp_data_path.pop_back(); } if (root-right) { binaryTreePaths(root-right); tmp_data_path.pop_back(); } return ret; } string makePath() { int size tmp_data_path.size(); std::string str; for (int i 0; i size; i) { if (i size - 1) { str std::to_string(tmp_data_path[i]) -; } else { str std::to_string(tmp_data_path[i]); } } return str; } private: vectorstring ret; vectorint tmp_data_path; };2.4 二叉树翻转力扣. - 力扣LeetCode/** * Definition for a binary tree node. * struct TreeNode { * 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) {} * }; */ class Solution { public: TreeNode* invertTree(TreeNode* root) { if (root nullptr) { return root; } TreeNode *left root-left; root-left root-right; root-right left; if (root-left) { invertTree(root-left); } if (root-right) { invertTree(root-right); } return root; } };3验证二叉搜索树98. 验证二叉搜索树 - 力扣LeetCode自己一开始没有想法没有思路看了题解之后想到还是用递归的方法来判断大小但是自己想的方法只能判断相邻两层的节点的大小关系如果跨几层的节点大小关系不满足那么是无法检测出来的。题解中的解法是每递归的时候看的都是一棵树给这一棵树限定它的上下界给整棵子树的上下限才是符合逻辑的。4二叉搜索树中第K小的元素230. 二叉搜索树中第 K 小的元素 - 力扣LeetCode前序中序后续一次就遍历一个节点就是root节点在一次递归计算中count只需要一次就可以了。/*** Definition for a binary tree node.* struct TreeNode {* 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) {}* };*/class Solution {public:int kthSmallest(TreeNode* root, int k) {//二叉搜索树root不小于left子树root不大于right子树//第k小的数中序遍历遍历到第一个就是这个数int count{0};impl(root, k, count);return ret_;}void impl(TreeNode *root, int const k, int count) {if (!root) {return;}if (root-left) {impl(root-left, k, count);}count;if (count k) {ret_ root-val;return;}if (root-right) {impl(root-right, k, count);}}int ret_{-1};};