当前位置： 首页 > news >正文

【算法篇】二叉树类（1）（笔记）

news 2026/1/15 14:29:36

目录

一、认识二叉树

1. 二叉树的种类

（1）满二叉树

（2）完全二叉树

（3）二叉搜索树

（4）平衡二叉搜索树

2. 二叉树的存储方式

3. 二叉树的遍历方式

4. 二叉树的定义

二、Leetcode 题目整理

1. 二叉树的前、中、后序遍历

（1）递归法

（2）迭代法（栈的运用）

（3）标记法（栈的运用）

2. 二叉树的层序遍历

（1）递归法

（2）迭代法

3. 翻转二叉树

（1）广度优先算法

（2）深度优先算法（前、中、后）

（3）递归法

4. 对称二叉树

（1）递归法

（2）迭代法

5. 二叉树的最大深度

6. 二叉树的最小深度

7. 平衡二叉树

8. 二叉树的所有路径

（1）回溯法

（2）迭代法

一、认识二叉树

1. 二叉树的种类

（1）满二叉树

        深度为 k，有 2^k-1 个节点的二叉树。

（2）完全二叉树

        在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（h从1开始），则该层包含 1~ 2^(h-1) 个节点。 

（3）二叉搜索树

二叉搜索树是一个有序树。

  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  • 它的左、右子树也分别为二叉排序树

（4）平衡二叉搜索树

        C++ 中 map、set、multimap，multiset 的底层实现都是 平衡二叉搜索树，所以map、set 的增删操作 时间时间复杂度 是 logn。

2. 二叉树的存储方式

        二叉树可以链式存储，也可以顺序存储。

        链式存储方式就用 指针， 顺序存储的方式就是用 数组。

        在数组存储中：如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。

3. 二叉树的遍历方式

二叉树主要有两种遍历方式：

  1. 深度优先遍历：先往深走，遇到叶子节点再往回走。
  2. 广度优先遍历：一层一层的去遍历。

从深度优先遍历和广度优先遍历进一步拓展，才有如下遍历方式：

  • 深度优先遍历
    • 前序遍历（递归法，迭代法）
    • 中序遍历（递归法，迭代法）
    • 后序遍历（递归法，迭代法）
  • 广度优先遍历
    • 层次遍历（迭代法）

4. 二叉树的定义

struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

二、Leetcode 题目整理

1. 二叉树的前、中、后序遍历

144. 二叉树的前序遍历 - 力扣（LeetCode）icon-default.png?t=O83Ahttps://leetcode.cn/problems/binary-tree-preorder-traversal/submissions/566103571/94. 二叉树的中序遍历 - 力扣（LeetCode）icon-default.png?t=O83Ahttps://leetcode.cn/problems/binary-tree-inorder-traversal/description/145. 二叉树的后序遍历 - 力扣（LeetCode）icon-default.png?t=O83Ahttps://leetcode.cn/problems/binary-tree-postorder-traversal/description/

        给你二叉树的根节点 root ，返回它节点值的 前序 / 中序 / 后序遍历。

（1）递归法

/*** 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:void traversal(TreeNode* cur, vector<int>& result) {if (cur == NULL) return;result.push_back(cur->val);traversal(cur->left, result);traversal(cur->right, result);}vector<int> preorderTraversal(TreeNode* root) {vector<int> result;traversal(root, result);return result;}
};// 中序遍历
class Solution {
public:void traversal(TreeNode* cur, vector<int>& result) {if (cur == NULL) return;traversal(cur->left, result);result.push_back(cur->val);traversal(cur->right, result);}vector<int> inorderTraversal(TreeNode* root) {vector<int> result;traversal(root, result);return result;}
};// 后序遍历
class Solution {
public:void traversal(TreeNode* cur, vector<int>& result) {if (cur == NULL) return;traversal(cur->left, result);traversal(cur->right, result);result.push_back(cur->val);}vector<int> postorderTraversal(TreeNode* root) {vector<int> result;traversal(root, result);return result;}
};

（2）迭代法（栈的运用）

/*** 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:vector<int> preorderTraversal(TreeNode* root) {stack<TreeNode*> record;vector<int> result;if (root == NULL) return result;record.push(root);while (!record.empty()) {TreeNode* node = record.top();record.pop();result.push_back(node->val);if (node->right) record.push(node->right);if (node->left) record.push(node->left);}return result;}
};// 中序遍历
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;TreeNode* cur = root;while (cur != NULL || !st.empty()) {if (cur != NULL) { // 指针来访问节点，访问到最底层st.push(cur);cur = cur->left;} else {cur = st.top(); // 从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）st.pop();result.push_back(cur->val);cur = cur->right;}}return result;}
};// 后序遍历（前序输出后翻转就可以）
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> st;vector<int> result;if (root == NULL) return result;st.push(root);while (!st.empty()) {TreeNode* node = st.top();st.pop();result.push_back(node->val);if (node->left) st.push(node->left); // 相对于前序遍历，这更改一下入栈顺序 （空节点不入栈）if (node->right) st.push(node->right); // 空节点不入栈}reverse(result.begin(), result.end()); // 将结果反转之后就是左右中的顺序了return result;}
};

（3）标记法（栈的运用）

        将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。如何标记呢，就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 

/*** 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:vector<int> preorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> record;if (root != nullptr) record.push(root);while (!record.empty()) {TreeNode* node = record.top();if (node != nullptr) {record.pop();if (node->right) record.push(node->right);if (node->left) record.push(node->left);record.push(node);record.push(nullptr);}else {record.pop();node = record.top();record.pop();result.push_back(node->val);}}return result;}
};// 中序遍历
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {// 标记法vector<int> result;stack<TreeNode*> record;if (root != nullptr) record.push(root);while (!record.empty()) {TreeNode* node = record.top();  // 等于nullptr，说明最先处理的节点已经遍历到。叶子结点已经到底，需要打印中间节点// 不等于nullptr，说明还未遍历到最先处理的节点if (node != nullptr) {record.pop(); // 弹出顶部元素，避免重复if (node->right) record.push(node->right);record.push(node);record.push(nullptr);if (node->left) record.push(node->left);}else {record.pop(); // 弹出nullptrnode = record.top();record.pop();result.push_back(node->val);}}return result;}
};// 后序遍历
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> record;if (root != nullptr) record.push(root);while (!record.empty()) {TreeNode* node = record.top();if (node != nullptr) {// 中 nullptr 右 左record.push(nullptr);if (node->right) record.push(node->right);if (node->left) record.push(node->left);}else {record.pop();node = record.top();record.pop();result.push_back(node->val);}}return result;}
};

2. 二叉树的层序遍历

102. 二叉树的层序遍历 - 力扣（LeetCode）icon-default.png?t=O83Ahttps://leetcode.cn/problems/binary-tree-level-order-traversal/description/

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

 

示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]示例 2：
输入：root = [1]
输出：[[1]]示例 3：
输入：root = []
输出：[]

（1）递归法

/*** 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:void order(TreeNode* cur, vector<vector<int>>& result, int depth){if (cur == nullptr) return;// 二叉树的层级是递增的（从根节点开始，逐层向下），且每个层级只会在第一次遇到时执行这行代码// 因此每个层级只会被添加一次对应的 vector<int>()if (result.size() == depth) result.push_back(vector<int>());result[depth].push_back(cur->val);order(cur->left, result, depth + 1);order(cur->right, result, depth + 1);}vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> result;int depth = 0;order(root, result, depth);return result;}
};

（2）迭代法

/*** 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:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> result;queue<TreeNode*> que;if (root != nullptr) que.push(root);while (!que.empty()) {// 现在que队列中的元素为当前层的节点个数int size = que.size();vector<int> record;for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();record.push_back(node->val);if (node->left) que.push(node->left);if (node->right) que.push(node->right);}result.push_back(record);}return result;}
};

3. 翻转二叉树

226. 翻转二叉树 - 力扣（LeetCode）icon-default.png?t=O83Ahttps://leetcode.cn/problems/invert-binary-tree/description/

        给你一棵二叉树的根节点 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]示例 3：
输入：root = []
输出：[]

        想要翻转它，其实就把每一个节点的左右孩子交换一下就可以了。 

（1）广度优先算法

/*** 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 || (!root->left && !root->right)) return root;queue<TreeNode*> que;que.push(root);while (!que.empty()) {int size = que.size();for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();swap(node->left, node->right);if (node->left) que.push(node->left);if (node->right) que.push(node->right);}}return root;}
};

（2）深度优先算法（前、中、后）

/*** 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) {// 后序遍历（循环法）stack<TreeNode*> record;if (root != nullptr) record.push(root);while (!record.empty()) {TreeNode* node = record.top();record.pop();if (node != nullptr) {// 栈顶元素不等于 nullptrrecord.push(node);                          // 中 record.push(nullptr);   // 到遍历中节点的时候停一下，需要先遍历右节点if (node->right) record.push(node->right);  // 右if (node->left) record.push(node->left);    // 左}else {node = record.top();record.pop();swap(node->left, node->right);}}return root;}
};class Solution {
public:TreeNode* invertTree(TreeNode* root) {// 中序遍历（循环法）stack<TreeNode*> record;if (root != nullptr) record.push(root);while (!record.empty()) {TreeNode* node = record.top();record.pop();if (node != nullptr) {// 栈顶元素不等于 nullptrif (node->right) record.push(node->right);  // 右record.push(node);                          // 中 record.push(nullptr);   // 遍历完左节点的时候停一下，现处理中节点if (node->left) record.push(node->left);    // 左}else {node = record.top();record.pop();swap(node->left, node->right);}}return root;}
};class Solution {
public:TreeNode* invertTree(TreeNode* root) {// 前序遍历（循环法）stack<TreeNode*> record;if (root != nullptr) record.push(root);while (!record.empty()) {TreeNode* node = record.top();record.pop();if (node != nullptr) {// 栈顶元素不等于 nullptrif (node->right) record.push(node->right);  // 右if (node->left) record.push(node->left);    // 左record.push(node);                          // 中   record.push(nullptr);}else {node = record.top();record.pop();swap(node->left, node->right);}}return root;}
};

（3）递归法

/*** 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 == NULL) return root;swap(root->left, root->right);  // 中invertTree(root->left);         // 左invertTree(root->right);        // 右return root;}
};

4. 对称二叉树

101. 对称二叉树 - 力扣（LeetCode）icon-default.png?t=O83Ahttps://leetcode.cn/problems/symmetric-tree/description/

        给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：
​​​​​​​输入：root = [1,2,2,null,3,null,3]
输出：false

（1）递归法

① 终止条件

  • 左节点为空，右节点不为空，不对称，return false
  • 左不为空，右为空，不对称 return false
  • 左右都为空，对称，返回true

② 单层递归的逻辑

         单层递归的逻辑就是处理 左右节点都不为空，且数值相同的情况。

  • 比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
  • 比较内侧是否对称，传入左节点的右孩子，右节点的左孩子。
  • 如果左右都对称就返回 true ，有一侧不对称就返回 false 。
/*** 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:bool compare(TreeNode* left, TreeNode* right) {// 判断条件if (left == nullptr && right != nullptr) return false;else if (left != nullptr && right == nullptr) return false;else if (left == nullptr && right == nullptr) return true;else if (left->val != right->val) return false;bool outside = compare(left->left, right->right);   // 外层判断bool inside = compare(left->right, right->left);    // 内层判断return (outside && inside);}bool isSymmetric(TreeNode* root) {// 递归法if (root == nullptr) return true;return compare(root->left, root->right);}
};

（2）迭代法

        通过队列来判断根节点的左子树和右子树的内侧和外侧是否相等。

/*** 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:bool isSymmetric(TreeNode* root) {if (root == nullptr) return true;queue<TreeNode*> que;que.push(root->left);que.push(root->right);while (!que.empty()) {TreeNode* leftnode = que.front(); que.pop();TreeNode* rightnode = que.front(); que.pop();if (leftnode == nullptr && rightnode != nullptr) return false;else if (leftnode != nullptr && rightnode == nullptr) return false;else if (leftnode == nullptr && rightnode == nullptr) continue;else if (leftnode->val != rightnode->val) return false;// 填入数据que.push(leftnode->left);que.push(rightnode->right);que.push(leftnode->right);que.push(rightnode->left);}return true;}
};

5. 二叉树的最大深度

104. 二叉树的最大深度 - 力扣（LeetCode）icon-default.png?t=O83Ahttps://leetcode.cn/problems/maximum-depth-of-binary-tree/description/

        给定一个二叉树 root ，返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：3示例 2：
输入：root = [1,null,2]
输出：2
/*** 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 maxDepth(TreeNode* root) {// 二叉树层序遍历queue<TreeNode*> que;int depth = 0;if (root == NULL) return depth;que.push(root);while(!que.empty()) {int size = que.size();depth++; // 记录深度for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();if (node->left) que.push(node->left);if (node->right) que.push(node->right);}}return depth;}
};

6. 二叉树的最小深度

111. 二叉树的最小深度 - 力扣（LeetCode）icon-default.png?t=O83Ahttps://leetcode.cn/problems/minimum-depth-of-binary-tree/description/

        给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

        说明：叶子节点是指没有子节点的节点。

示例 1：
​​​​​​​输入：root = [3,9,20,null,null,15,7]
输出：2示例 2：
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5
/*** 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 minDepth(TreeNode* root) {// 层序遍历int depth = 0;queue<TreeNode*> que;if (root == NULL) return 0;que.push(root);while(!que.empty()) {int size = que.size();depth++; // 记录最小深度for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();if (node->left) que.push(node->left);if (node->right) que.push(node->right);if (!node->left && !node->right) { // 当左右孩子都为空的时候，说明是最低点的一层了，退出return depth;}}}return depth;}
};

7. 平衡二叉树

110. 平衡二叉树 - 力扣（LeetCode）icon-default.png?t=O83Ahttps://leetcode.cn/problems/balanced-binary-tree/description/

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

示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：
​​​​​​​输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
示例 3：
输入：root = []
输出：true

  思路：

（1）明确递归函数的参数 和 返回值

        参数：当前传入节点。         返回值：以当前传入节点为根节点的树的高度。

        如果已经不是二叉平衡树了，可以返回-1 来标记已经不符合平衡树的规则了。

（2）明确终止条件

        递归的过程中 依然是遇到 空节点了为终止，返回 0，表示 当前节点为 根节点的 树高度为0。

（3）明确单层递归的逻辑

        分别求出其左右子树的高度，然后如果差值小于 等于1，则返回当前二叉树的高度，否则返回-1，表示已经 不是二叉平衡树了。

/*** 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 getHeight(TreeNode* node) {     // 后序遍历if (node == nullptr) return 0;int leftNum = getHeight(node->left);if (leftNum == -1) return -1;int rightNum = getHeight(node->right);if (rightNum == -1) return -1;// 子树拥有的层数越多，高度越高return abs(leftNum - rightNum) > 1 ? -1 : 1 + max(leftNum, rightNum);}bool isBalanced(TreeNode* root) {// 回溯法return getHeight(root) == -1 ? false : true;}
};

8. 二叉树的所有路径

257. 二叉树的所有路径 - 力扣（LeetCode）icon-default.png?t=O83Ahttps://leetcode.cn/problems/binary-tree-paths/description/

        给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。叶子节点 是指没有子节点的节点。

示例 1：
输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]示例 2：
输入：root = [1]
输出：["1"]

（1）回溯法

        这道题目要求 从根节点到叶子的路径，所以需要 前序遍历，这样才 方便让父节点 指向孩子 节点，找到 对应的路径。我们 要把路径 记录下来，需要 回溯来回退一个 路径 再进入另一个路径。

/*** 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:void TreePath(TreeNode* node, vector<string>& path, string str) {str = str + to_string(node->val);if (!node->left && !node->right) {path.push_back(str);return;}if (node->left) TreePath(node->left, path, str + "->");if (node->right) TreePath(node->right, path, str + "->");}vector<string> binaryTreePaths(TreeNode* root) {// 前序遍历vector<string> result;if (root == nullptr) return result;TreePath(root, result, "");return result;}
};

（2）迭代法

/*** 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:vector<string> binaryTreePaths(TreeNode* root) {stack<TreeNode*> treeSt;// 保存树的遍历节点stack<string> pathSt;   // 保存遍历路径的节点vector<string> result;  // 保存最终路径集合if (root == NULL) return result;treeSt.push(root);pathSt.push(to_string(root->val));while (!treeSt.empty()) {TreeNode* node = treeSt.top(); treeSt.pop(); // 取出节点 中string path = pathSt.top();pathSt.pop();    // 取出该节点对应的路径if (node->left == NULL && node->right == NULL) { // 遇到叶子节点result.push_back(path);}if (node->right) { // 右treeSt.push(node->right);pathSt.push(path + "->" + to_string(node->right->val));}if (node->left) { // 左treeSt.push(node->left);pathSt.push(path + "->" + to_string(node->left->val));}}return result;}
};

相关文章：

【算法篇】二叉树类（1）（笔记）

目录 一、认识二叉树 1. 二叉树的种类 &#xff08;1&#xff09;满二叉树 &#xff08;2&#xff09;完全二叉树 &#xff08;3&#xff09;二叉搜索树 &#xff08;4&#xff09;平衡二叉搜索树 2. 二叉树的存储方式 3. 二叉树的遍历方式 4. 二叉树的定义 二、Leet…...

编程日记 2024/9/27 11:15:59

《C++无锁编程：解锁高性能并发的新境界》

在当今的软件开发领域&#xff0c;并发编程的重要性日益凸显。随着多核处理器的普及&#xff0c;开发者们越来越需要利用并发来提高程序的性能和响应速度。而 C作为一种强大的编程语言&#xff0c;提供了多种技术来实现无锁编程&#xff0c;从而在并发环境下获得更高的性能和更…...

编程日记 2024/9/27 11:14:58

系统架构设计师教程 第9章 9.5 软件可靠性测试 笔记

9.5 软件可靠性测试 ★★★☆☆ 9.5.1 软件可靠性测试概述 软件测试者可以使用很多方法进行软件测试&#xff0c;如按行为或结构来划分输入域的划分测试&#xff0c; 纯粹随机选择输入的随机测试&#xff0c;基于功能、路径、数据流或控制流的覆盖测试等。 软件可靠性测试由可…...

编程日记 2024/9/27 11:13:57

如何使用ssm实现校园体育赛事管理系统的设计与实现+vue

TOC ssm713校园体育赛事管理系统的设计与实现vue 绪论 课题背景 身处网络时代&#xff0c;随着网络系统体系发展的不断成熟和完善&#xff0c;人们的生活也随之发生了很大的变化。目前&#xff0c;人们在追求较高物质生活的同时&#xff0c;也在想着如何使自身的精神内涵得…...

编程日记 2024/9/27 11:11:55

CSS 中的文本相关属性（line - height、font、letter - 属性、text - 属性）

目录 非 VIP 用户可前往公众号回复“css”进行免费阅读 line - height属性 字号与行高的取值约定 行高与盒子高度的关系 font、letter -属性 、text -属性 font属性 letter -属性 text - 属性 非 VIP 用户可前往公众号回复“css”进行免费阅读 line - height属性 字号与…...

编程日记 2024/9/27 11:10:54

mobaxterm、vscode通过跳板机连接服务器

目标服务器&#xff1a;111.111.11.11 跳板机&#xff1a;100.100.10.10 1. mobaxterm通过跳板机连接服务器 1.1 目标服务器信息 1.2 跳板机信息 1.3 登录 点击登录&#xff0c;会输入密码&#xff0c;成功 参考&#xff1a;https://blog.csdn.net/qq_40636486/article/det…...

编程日记 2024/9/27 11:08:50

鸿萌数据恢复：iPhone 手机被盗后应采取哪些措施？警惕这些骗局

天津鸿萌科贸发展有限公司从事数据安全服务二十余年&#xff0c;致力于为各领域客户提供专业的数据恢复、数据备份解决方案与服务&#xff0c;并针对企业面临的数据安全风险&#xff0c;提供专业的相关数据安全培训。 丢失昂贵的 iPhone 不仅会造成较大的经济损失&#xff0c;还…...

编程日记 2024/9/27 11:06:48

为了学习Python熬夜部署了Jupyter Notebook 6.x

文章目录 Docker拉取并构建容器安装部署jupyter对Jupyter使用过程问题总结1 没有代码提示怎么办&#xff1f;2 如果想切换python版本了怎么办&#xff1f;3 想在jupyter里面使用vim怎么办&#xff1f; 遇见的问题参考文章 怎么说&#xff0c;今天在学习Python的时候&#xff0c…...

编程日记 2024/9/27 11:03:44

docker-文件复制（docker cp：用于在Docker主机和容器之间拷贝文件或目录）

文章目录 1、把宿主机的文件复制到容器内部1.1、查询 宿主机 root 下的文件1.2、docker cp /root/anaconda-ks.cfg spzx-redis:/root1.3、查看 spzx-redis 容器 中/root目录下是否有 anaconda-ks.cfg 文件 2、把容器中的文件 复制 到宿主机中2.1、查看 spzx-redis 容器 / 下的文…...

编程日记 2024/9/27 11:02:43

guava里常用功能

guava 是 Google 提供的一个 Java 库&#xff0c;提供了很多实用的工具类和方法&#xff0c;可以帮助开发者更高效地编写代码。以下是一些常用的 Guava 工具类及其功能示例&#xff1a; 1. Lists 用于操作列表的工具类。 import com.google.common.collect.Lists;List<In…...

编程日记 2024/9/27 11:01:42

su 命令：一键切换用户身份、提高su命令安全性的建议

一、命令简介 ​su ​命令是 Linux 和 Unix 系统中的一个实用工具&#xff0c;用于切换用户身份。它允许当前登录用户在不退出登录会话的情况下&#xff0c;切换到另一个用户的身份。通常&#xff0c;su ​用于从普通用户切换到 root 用户&#xff0c;或从 root 用户切换到其他…...

编程日记 2024/9/27 10:58:39

观察者模式（发布-订阅模式）

用途&#xff1a; &#xff08;1&#xff09;可用于拦截过滤器 &#xff08;2&#xff09;订单创建成功后的一些后续逻辑&#xff08;消息提醒&#xff0c;订单打印&#xff0c;物品打包等&#xff09; &#xff08;3&#xff09;需要由统一调度中心调度的一系列任务等 消息…...

编程日记 2024/9/27 10:57:38

耦合微带线单元的网络参量和等效电路公式推导

文档下载链接&#xff1a;耦合微带线单元的网络参量和等效电路资源-CSDN文库https://download.csdn.net/download/lu2289504634/89583027笔者水平有限&#xff0c;错误之处欢迎留言&#xff01; 一、耦合微带线奇偶模详细推导过程 二、2,4端口开路 三、2端口短路、3端口开路 四…...

编程日记 2024/9/27 10:56:37

elasticsearch的Ingest Attachment插件的使用总结

安装 Ingest Attachment 插件 确保 Elasticsearch 已安装&#xff1a; 首先&#xff0c;请确保你已经安装并运行了 Elasticsearch。可以通过访问 http://localhost:9200 来检查是否正常运行。 安装插件&#xff1a; 使用以下命令在 Elasticsearch 中安装 Ingest Attachment 插…...

编程日记 2024/9/27 10:55:34

SemiDrive E3 MCAL 开发系列（4） – Gpt 模块的使用

一、 概述 本文将会介绍SemiDrive E3 MCAL GPT模块的基本配置&#xff0c;并且会结合实际操作的介绍&#xff0c;帮助新手快速了解并掌握这个模块的使用&#xff0c;文中的 MCAL 是基于 PTG3.0 的版本&#xff0c;开发板是官方的 E3640 网关板。 二、 Gpt 模块的主要配置 …...

编程日记 2024/9/27 10:54:33

前端导出页面PDF

import html2canvas from html2canvas import { jsPDF } from jspdf import { Loading } from element-ui let downloadLoadingInstance// 导出页面为PDF格式---使用插件html2canvas和jspdf插件 export function exportPDF(fileName, node) {downloadLoadingInstance Loading.…...

编程日记 2024/9/27 10:53:32

Jenkins的安装

1.简介 官网&#xff1a;https://www.jenkins.io 中文文档&#xff1a;Jenkins Jenkins 是一个开源的持续集成&#xff08;CI&#xff09;工具&#xff0c;用于自动化构建、测试和部署软件项目。它提供了一个易于使用和可扩展的平台&#xff0c;帮助团队更高效地开发和交付软…...

编程日记 2024/9/27 10:52:31

初学51单片机之I2C总线与E2PROM

首先先推荐B站的I2C相关的视频I2C入门第一节-I2C的基本工作原理_哔哩哔哩_bilibili 看完视频估计就大概知道怎么操作I2C了&#xff0c;他的LCD1602讲的也很不错&#xff0c;把数据建立tsp和数据保持thd&#xff0c;比喻成拍照时候的摆pose和按快门两个过程&#xff0c;感觉还是…...

编程日记 2024/9/27 10:50:29

C语言数组探秘：数据操控的艺术【下】

承接上篇&#xff0c;我们继续讲数组的内容。 八.二维数组的使用 当我们掌握了二维数组的创建和初始化&#xff0c;那我们怎么使用二维数组呢&#xff1f;其实二维数组访问也是使用下标的形式的&#xff0c;二维数组是有行和列的&#xff0c;只要锁定了行和列就能唯一锁定数组中…...

编程日记 2024/9/27 10:49:28

Jmeter关联，断言，参数化

目录 一、关联 边界提取器 JSON提取器 正则表达式提取器 跨线程关联 二、断言 响应断言 JSON断言 断言持续时间 三、参数化 用户参数 csv data setconfig csvread函数 一、关联 常用的关联有三种 1.边界提取器 2.JSON提取器 3.正则表达式提取器 接下来就详细讲述…...

编程日记 2024/9/27 10:48:27

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

编程新知 2026/1/15 4:24:12

逻辑回归：给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

编程新知 2025/10/27 21:25:04

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

编程新知 2026/1/15 6:07:16

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

编程新知 2026/1/15 4:57:43

CRMEB 框架中 PHP 上传扩展开发：涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

编程新知 2025/12/30 22:56:56

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中，常常会遇到 跨域请求接口 的情况。为了解决这个问题，Vite 和 Webpack 都提供了 proxy 代理功能，用于将本地开发请求转发到后端服务器。 什么是代理（proxy）？ 代理是在开发过程中，前端项目通过开发服务器，将指定的请求“转发”到真实的后端服务器，从而绕…...

编程新知 2025/10/27 20:33:34

学校时钟系统，标准考场时钟系统，AI亮相2025高考，赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

编程新知 2026/1/15 5:44:15

Android第十三次面试总结（四大 组件基础）

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

编程新知 2025/10/15 15:07:34

高效线程安全的单例模式：Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式：Python 中的懒加载与自定义初始化参数 在软件开发中，单例模式（Singleton Pattern）是一种常见的设计模式，确保一个类仅有一个实例，并提供一个全局访问点。在多线程环境下，实现单例模式时需要注意线程安全问题，以防止多个线程同时创建实例，导致…...

编程新知 2025/11/25 19:50:27

Java数值运算常见陷阱与规避方法

整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时，会出现小数部分被截断的情况。典型错误模式如下： void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...

编程新知 2025/9/29 10:54:34