# 回溯算法的理论 回溯和递归类似，都不是很高效 回溯法，一般可以解决如下几种问题： 组合问题：N 个数里面按一定规则找出 k 个数的集合 切割问题：一个字符串按一定规则有几种切割方式 子集问题：一个 N 个数的集合里有多少符合条件的子集 排列问题：N 个数按一定规则全排列，有几种排列方式 棋盘问题：N 皇后，解数独等等 回溯法解决的问题都可以抽象为树形结构 # 回溯模板 函数名习惯定义为 backtracking，返回值一般 void，参数根据逻辑需要什么补充什么 回溯函数伪代码如下 void backtracking(参数)回溯函数终止条件 if (终止条件) {...

# 题目 给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。 叶子节点 是指没有子节点的节点。 示例 1： 输入：root = [1,2,3,null,5] 输出：["1->2->5","1->3"] 示例 2： 输入：root = [1] 输出：["1"] 257. 二叉树的所有路径 - 力扣（LeetCode） #...

# 题目 给定一个二叉树，判断它是否是高度平衡的二叉树。 本题中，一棵高度平衡二叉树定义为： 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 示例 1： 输入：root = [3,9,20,null,null,15,7] 输出：true 110. 平衡二叉树 - 力扣（LeetCode） # 分析 递归 class Solution {public: // 返回以该节点为根节点的二叉树的高度，如果不是平衡二叉树了则返回 - 1 int getHeight(TreeNode* node) { if (node == NULL)...

# 题目 给出一个完全二叉树，求出该树的节点个数。 示例 1： 输入：root = [1,2,3,4,5,6] 输出：6 示例 2： 输入：root = [] 输出：0 示例 3： 输入：root = [1] 输出：1 提示： 树中节点的数目范围是 [0, 5 * 10^4] 0 <= Node.val <= 5 * 10^4 题目数据保证输入的树是 完全二叉树 222. 完全二叉树的节点个数 - 力扣（LeetCode） #...

# 题目 给你一个二叉树的根节点 root ， 检查它是否轴对称。 示例 1： 输入：root = [1,2,2,3,4,4,3] 输出：true 示例 2： 输入：root = [1,2,2,null,3,null,3] 输出：false 提示： 树中节点数目在范围 [1, 1000] 内 -100 <= Node.val <= 100 ** 进阶：** 你可以运用递归和迭代两种方法解决这个问题吗？ # 分析 镜像对称，我们需要比较二叉树的外侧和内侧是否都相等 本题遍历只能是...

# 题目 你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。 示例 1： 输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1] 示例 2： 输入：root = [2,1,3] 输出：[2,3,1] 226. 翻转二叉树 - 力扣（LeetCode） # 分析 翻转二叉树其实就是把每个节点的左右孩子互换即可 递归法： class Solution {public: TreeNode* invertTree(TreeNode* root) { if (root == NULL) return root;...

# 题目 给定一个二叉树，找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明：叶子节点是指没有子节点的节点。 示例 2： 输入：root = [1,null,2] 输出：2 104. 二叉树的最大深度 - 力扣（LeetCode） 给定一个二叉树，找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 ** 说明：** 叶子节点是指没有子节点的节点。 示例 1： 输入：root = [3,9,20,null,null,15,7] 输出：2 示例 2： 输入：root =...

# 题目 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。 示例 1： 输入：root = [1] 输出：[[1]] 示例 2： 输入：root = [] 输出：[] 提示： 树中节点数目在范围 [0, 2000] 内 -1000 <= Node.val <= 1000 102. 二叉树的层序遍历 - 力扣（LeetCode） # 分析 层序遍历其实就是广度优先遍历，队列先进先出，符合一层一层遍历的逻辑，而栈先进后出符合深度优先遍历的逻辑 class Solution {public:...

# 题目 不用递归实现二叉树的前中后遍历 # 分析 递归的本质是每次递归就把函数的局部变量、参数值和返回地址压入调用栈中，递归返回时，栈顶再弹出上一次递归各项值。 所以用栈也可以实现前中后遍历 前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。 为什么要先加入 右孩子，再加入左孩子呢？ 因为这样出栈的时候才是中左右的顺序。 class Solution {public: vector<int> preorderTraversal(TreeNode* root) {...

# 题目 实现二叉树的递归遍历 # 分析 遍历分为前序遍历，即中左右；中序遍历，左中右；后续遍历，左右根 递归实现，需要清楚递归三要素： 1. 递归函数的参数和返回值 2. 终止条件 3. 单层递归的逻辑 // 前序遍历class Solution {public: void traversal(TreeNode* cur, vector<int>& vec) { if (cur == NULL) return; vec.push_back(cur->val); // 中...