二叉树

知识点

二叉树遍历

前序遍历：先访问根节点，再前序遍历左子树，再前序遍历右子树

中序遍历：先中序遍历左子树，再访问根节点，再中序遍历右子树

后序遍历：先后序遍历左子树，再后序遍历右子树，再访问根节点

注意点

以根访问顺序决定是什么遍历左子树都是优先右子树

前序递归

二叉树的前序遍历

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> ve; vector<int> preorderTraversal(TreeNode* root) { if(root) { ve.push_back(root -> val); preorderTraversal(root -> left); preorderTraversal(root -> right); } return ve; } };

前序非递归（迭代法）

class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> ve; if(root == NULL) return ve; vector<TreeNode*> stk; stk.push_back(root); while(!stk.empty()){ TreeNode* tmp = stk.back(); stk.pop_back(); ve.push_back(tmp -> val); if(tmp -> right){ stk.push_back(tmp -> right); } if(tmp -> left){ stk.push_back(tmp -> left); } } return ve; } };

中序非递归（迭代法）

二叉树的中序遍历

/* 思路：每到一个节点 A，因为根的访问在中间，将 A 入vector。 * 然后遍历左子树，接着访问 A，最后遍历右子树。 * 在访问完 A 后，A 就可以出vector了。因为 A 和其左子树都已经访问完成。 * 和前序类似 */ class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<TreeNode*> ve; vector<int> v; TreeNode* rt = root; while(rt || !ve.empty()) { while(rt) { ve.push_back(rt); rt=rt->left; } rt=ve.back(); ve.pop_back(); v.push_back(rt->val); rt=rt->right; } return v; } };

后序非递归（迭代法）

二叉树的后序遍历

class Solution { public: vector<int> postorderTraversal(TreeNode* root) { vector<int> res; if(root == NULL) return res; vector<TreeNode*> stk; stk.push_back(root); while(!stk.empty()){ TreeNode* tmp = stk.back(); stk.pop_back(); if(tmp!=nullptr){ stk.push_back(tmp); stk.push_back(nullptr); if(tmp -> right) stk.push_back(tmp -> right); if(tmp -> left) stk.push_back(tmp -> left); } else{ res.push_back(stk.back()->val); stk.pop_back(); } } return res; } };

注意点

核心就是：根节点必须在右节点弹出之后，再弹出

DFS 深度搜索-从上到下

二叉树的前序遍历

class Solution { public: // 深度遍历，结果指针作为参数传入到函数内部 void dfs(TreeNode* root, vector<int>* result){ if(root){ result -> push_back(root -> val); dfs(root -> left, result); dfs(root -> right, result); } } vector<int> preorderTraversal(TreeNode* root){ vector<int> res; dfs(root, &res); return res; } };

这实际上就是递归的实现

DFS 深度搜索-从下向上（分治法）

二叉树的前序遍历

分治法模板

递归返回条件分段处理合并结果 Type traversal(TreeNode* root) { // NULL or leaf if(root == NULL) { // do something and return } // Divide Type left = traversal(root -> Left) Type right = traversal(root -> Right) // Conquer Type result = Merge from left and right return result }

答案代码

class Solution { public: vector<int> divideAndConquer(TreeNode* root){ vector<int> result; if(root != NULL){ vector<int> r_left = divideAndConquer(root -> left); vector<int> r_right = divideAndConquer(root -> right); result.push_back(root -> val); for(auto it : r_left){ result.push_back(it); } for(auto it : r_right){ result.push_back(it); } } return result; } vector<int> preorderTraversal(TreeNode* root){ vector<int> res; res = divideAndConquer(root); return res; } };

注意点：

DFS 深度搜索（从上到下） 和分治法区别：前者一般将最终结果通过指针参数传入，后者一般递归返回结果最后合并

BFS 层次遍历

二叉树的层次遍历 II

给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

思路：在层级遍历的基础上，翻转一下结果即可

class Solution { public: vector<vector<int>> levelOrderBottom(TreeNode* root) { queue<TreeNode*> q; vector<vector<int>> result; if(!root){ return result; } q.push(root); while(!q.empty()){ vector<int> ve; int nums = q.size(); for(int i = 0; i < nums; i++){ TreeNode* tmp = q.front(); q.pop(); ve.push_back(tmp->val); if(tmp->left){ q.push(tmp->left); } if(tmp->right){ q.push(tmp->right); } } result.insert(result.begin(), ve); } return result; } };

分治法应用

先分别处理局部，再合并结果

适用场景

归并排序

快速排序

二叉树相关问题

归并排序

​ 归并排序是典型分治思想的代表——首先把原问题分解为两个或多个子问题，然后求解子问题的解，最后使用子问题的解来构造出原问题的解。 ​ 对于归并排序，给定一个待排序的数组，首先把该数组划分为两个子数组，然后对子数组进行排序（递归调用归并排序），最后对两个有序的子数组进行合并，使合并之后的数组为有序状态。 ​ 让我们想想，把一个数组不断地划分为子数组，不断地划分…,不断地划分…, 最后停止了划分不下去了。 此时子数组的元素有一个，它们本身就是有序的。接下来，我们就需要执行合并过程，不断地一层层向上合并，…, 直到原数组。通过这个过程就会发现， 归并排序的核心在于合并有序的子数组，而不是对子数组进行排序，因为最底层的子数组本身就是有序的，上一层子数组如果想要变成有序的，通过合并底层有序的子数组就可以得到， 最终我们使原数组变成了有序的，从而完成了排序操作。

归并排序是用分治思想，时间复杂度为O(NlogN)。分治模式在每一层递归上有三个步骤：

分解（Divide）：将n个元素分成个含n/2个元素的子序列。解决（Conquer）：用合并排序法对两个子序列递归的排序。合并（Combine）：合并两个已排序的子序列已得到排序结果。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8YqXYlLH-1602146013339)(E:\zhan\算法模板编写\img\归并排序.webp)]

#include <cstring> #include <iostream> typedef bool (*CompareFunc)(int, int); // 下面函数实现合并功能，输入三个下标参数表示了两个子数组, :[nStart_, nMiddle)和[nMiddle, nEnd) void Merge(int array[], int nStart_, int nMiddle_, int nEnd_, CompareFunc comp) { if (array == nullptr || nStart_ >= nMiddle_ || nMiddle_ >= nEnd_) return; // 建立一个临时数组存放中间数据 int _nIndex = 0; int* _pTempArray = new int[nEnd_ - nStart_]; // 对两个子数组进行合并 int _nStartChange = nStart_; int _nMiddleChange = nMiddle_; while (_nStartChange < nMiddle_ && _nMiddleChange < nEnd_) { // 此处的if中比较语句的安排可以保持稳定排序的特性。 if (comp(array[_nMiddleChange], array[_nStartChange])) { _pTempArray[_nIndex] = array[_nMiddleChange]; ++_nMiddleChange; } else { _pTempArray[_nIndex] = array[_nStartChange]; ++_nStartChange; } ++_nIndex; } // 把不为空的子数组的元素追加到临时数 if (_nStartChange < nMiddle_) { memcpy(_pTempArray + _nIndex, array + _nStartChange, sizeof(int) * (nMiddle_ - _nStartChange)); } else if (_nMiddleChange < nEnd_) { memcpy(_pTempArray + _nIndex, array + _nMiddleChange, sizeof(int) * (nEnd_ - _nMiddleChange)); } else { /* do noting */ } // 数据交换 memcpy(array + nStart_, _pTempArray, sizeof(int) * (nEnd_ - nStart_)); delete[] _pTempArray; _pTempArray = nullptr; } // 归并排序功能实现函数 void MergeSort(int array[], int nStart_, int nEnd_, CompareFunc comp) { // 数组指针为空，或者数组内的个数少于等于1个时，直接返回。 if (nullptr == array || (nEnd_ - nStart_) <= 1) return; // 划分为两个子数组并递归调用自身进行排序 int _nMiddle = (nStart_ + nEnd_) / 2; MergeSort(array, nStart_, _nMiddle, comp); MergeSort(array, _nMiddle, nEnd_, comp); // 合并排序完成的子数组 Merge(array, nStart_, _nMiddle, nEnd_, comp); } // 比较函数 bool less(int lhs, int rhs) { return lhs < rhs; } bool large(int lhs, int rhs) { return lhs > rhs; } // 打印数组函数 void PrintArray(int array[], int nLength_) { if (nullptr == array || nLength_ <= 0) return; for (int i = 0; i < nLength_; ++i) { std::cout << array[i] << " "; } std::cout << std::endl; } /*************** main.c *********************/ int main(int argc, char* argv[]) { // 测试 int array[10] = {1, -1, 1, 5, -5, -1, -1, 3, -4, -2}; MergeSort(array, 0, 9, large); PrintArray(array, 10); return 0; }

快速排序

​ 快速排序作为20世纪十大算法之一，我们这些玩编程的好像没有理由不去学习它。快速排序是冒泡排序的升级版。

​ 基本思想：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可以分别对这两部分记录继续进行排序，以达到整个序列有序的目的。可参考这位大佬

#include <iostream> typedef bool (*CompareFunc)(int, int); // 比较函数 bool less(int lhs, int rhs) { return lhs <= rhs; } // 从小到大 bool large(int lhs, int rhs) { return lhs >= rhs; } // 从大到小 void quickSort(int left, int right, int arr[], CompareFunc comp) { // 递归边界条件 if (left >= right) return; int i, j, base, temp; i = left, j = right; base = arr[left]; //取最左边的数为基准数 while (i < j) { while (comp(base, arr[j]) && i < j) j--; while (comp(arr[i], base) && i < j) i++; if (i < j) { temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } //基准数归位 arr[left] = arr[i]; arr[i] = base; quickSort(left, i - 1, arr, comp); //递归左边 quickSort(i + 1, right, arr, comp); //递归右边 } // 打印数组函数 void PrintArray(int array[], int nLength_) { if (nullptr == array || nLength_ <= 0) return; for (int i = 0; i < nLength_; ++i) { std::cout << array[i] << " "; } std::cout << std::endl; } int main(int argc, char* argv[]) { // 测试 int array[10] = {1, -1, 1, 5, -5, -1, -1, 3, -4, -2}; quickSort(0, 9, array, less); PrintArray(array, 10); quickSort(0, 9, array, large); PrintArray(array, 10); return 0; }

注意点：

快排由于是原地交换所以没有合并过程 传入的索引是存在的索引（如：0、length-1 等），越界可能导致崩溃

常见题目示例

二叉树的最大深度

给定一个二叉树，找出其最大深度。

思路：分治法

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int maxDepth(TreeNode* root) { if(!root) return 0; if(!root -> left && !root -> right) return 1; // divide：分左右子树分别计算 int left = maxDepth(root -> left); int right = maxDepth(root -> right); // conquer：合并左右子树结果 return left > right ? left + 1 : right + 1; } };

平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

思路：分治法，左边平衡 && 右边平衡 && 左右两边高度 <= 1， 因为需要返回是否平衡及高度，要么返回两个数据，要么合并两个数据， 所以用-1 表示不平衡，>0 表示树高度（二义性：一个变量有两种含义）。

class Solution { public: bool isBalanced(TreeNode* root) { if(maxDepth(root) == -1) { return false; } return true; } int maxDepth(TreeNode* root) { if(!root) return 0; if(!root -> left && !root -> right) return 1; int left = maxDepth(root -> left); int right = maxDepth(root -> right); // 为什么返回-1呢？因为高度不可能为负数 if(abs(left - right) > 1 || left == -1 || right == -1) { return -1; } return left > right ? left + 1 : right + 1; } };

注意

一般工程中，结果通过两个变量来返回，不建议用一个变量表示两种含义

二叉树中的最大路径和

给定一个非空二叉树，返回其最大路径和。

思路：分治法，分为三种情况：左子树最大路径和最大，右子树最大路径和最大，左右子树最大加根节点最大，需要保存两个变量：一个保存子树最大路径和，一个保存左右加根节点和，然后比较这个两个变量选择最大值即可

class Solution { public: struct ResultType { int SinglePath; // 保存单边最大值 int MaxPath; // 保存最大值（单边或者两个单边+根的值） }; ResultType helper(TreeNode* root) { if(root == NULL) { return {0,-(1 << 10)}; } // Divide ResultType left = helper(root -> left); ResultType right = helper(root -> right); // Conquer ResultType result; // 求单边最大值 if(left.SinglePath > right.SinglePath) { result.SinglePath = std::max(left.SinglePath + root -> val, 0); } else { result.SinglePath = std::max(right.SinglePath + root -> val, 0); } // 求两边加根最大值 int tempMax = std::max(right.MaxPath, left.MaxPath); result.MaxPath = std::max(tempMax, left.SinglePath + right.SinglePath + root -> val); return result; } int maxPathSum(TreeNode* root) { ResultType result = helper(root); return result.MaxPath; } };

二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

思路：分治法，有左子树的公共祖先或者有右子树的公共祖先，就返回子树的祖先，否则返回根节点

class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { // 相等 直接返回root节点即可 if(root == NULL || root == p || root == q) { return root; } // Divide TreeNode* left = lowestCommonAncestor(root -> left, p, q); TreeNode* right = lowestCommonAncestor(root -> right, p, q); // Conquer // 左右两边都不为空，则根节点为祖先 if(left != NULL && right != NULL) { return root; } if(left != NULL) { return left; } if(right != NULL) { return right; } return NULL; } };

BFS 层次应用

二叉树的层序遍历

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）

思路：用一个队列记录一层的元素，然后扫描这一层元素添加下一层元素到队列（一个数进去出来一次，所以复杂度 O(logN)）。(和之前的二叉树的层次遍历 II类似)

class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { queue<TreeNode*> q; vector<vector<int>> result; if(!root){ return result; } q.push(root); while(!q.empty()){ vector<int> ve; int nums = q.size(); for(int i = 0; i < nums; i++){ TreeNode* tmp = q.front(); q.pop(); ve.push_back(tmp->val); if(tmp->left){ q.push(tmp->left); } if(tmp->right){ q.push(tmp->right); } } result.push_back(ve); } return result; } };

二叉树的锯齿形层次遍历

给定一个二叉树，返回其节点值的锯齿形层次遍历。Z 字形遍历

思路：在层次遍历的基础上加个下一层反向

class Solution { public: vector<vector<int>> zigzagLevelOrder(TreeNode* root) { queue<TreeNode*> q; vector<vector<int>> result; if(!root){ return result; } q.push(root); bool reverse_flag = false; while(!q.empty()){ vector<int> ve; int nums = q.size(); for(int i = 0; i < nums; i++){ TreeNode* tmp = q.front(); q.pop(); ve.push_back(tmp->val); if(tmp->left){ q.push(tmp->left); } if(tmp->right){ q.push(tmp->right); } } if(reverse_flag) { std::reverse(ve.begin(), ve.end()); reverse_flag = false; } else { reverse_flag = true; } result.push_back(ve); } return result; } };

二叉搜索树应用

验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

思路 1：递归

思路 2：中序遍历，检查结果列表是否已经有序

思路 3：分治法，判断左 MAX < 根 < 右 MIN

// v1 class Solution { public: bool isBSTUtil(TreeNode* root, long min, long max) { if(root == NULL) return true; if(root->val <= min || root->val >= max) return false; return isBSTUtil(root->left, min, root->val) && isBSTUtil(root->right, root->val, max); } bool isValidBST(TreeNode* root) { long v_min = LONG_MIN, v_max = LONG_MAX; return isBSTUtil(root, v_min, v_max); } }; // v2 class Solution { public: bool isValidBST(TreeNode* root) { if(root == NULL) { return true; } vector<int> result; inOrder(root, &result); // 按左、根、右排列进行比较，左大于根或者根大于右则肯定不是平衡二叉树 for(int i = 0; i < result.size() - 1; i++) { if(result[i] >= result[i + 1]) { return false; } } return true; } // 分别将左节点和右节点放入result void inOrder(TreeNode* root, vector<int>* result) { if(root == NULL) { return; } inOrder(root -> left, result); result -> push_back(root -> val); inOrder(root -> right, result); } }; // v3 class Solution { public: struct ResultType { bool IsValid; // 记录左右两边最大最小值，和根节点进行比较 TreeNode* Max; TreeNode* Min; }; bool isValidBST(TreeNode* root) { ResultType result = helper(root); return result.IsValid; } ResultType helper(TreeNode* root) { ResultType result = {}; if(root == NULL) { result.IsValid = true; return result; } ResultType left = helper(root -> left); ResultType right = helper(root -> right); if(!left.IsValid || !right.IsValid) { result.IsValid = false; return result; } if(left.Max != NULL && (left.Max -> val) >= (root -> val)) { result.IsValid = false; return result; } if(right.Min != NULL && right.Min -> val <= root -> val) { result.IsValid = false; return result; } result.IsValid = true; // 如果左边还有更小的3，就用更小的节点，不用4 // 5 // / \ // 1 4 // / \ // 3 6 result.Min = root; if(left.Min != NULL) { result.Min = left.Min; } result.Max = root; if(right.Max != NULL) { result.Max = right.Max; } return result; } };

二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。

思路：找到最后一个叶子节点满足插入条件即可

class Solution { public: TreeNode* insertIntoBST(TreeNode* root, int val) { if(root == NULL) { return new TreeNode(val); } if(root -> val > val) { root -> left = insertIntoBST(root -> left, val); } else { root ->right = insertIntoBST(root -> right, val); } return root; } };

总结

掌握二叉树递归与非递归遍历理解 DFS 前序遍历与分治法理解 BFS 层次遍历