二叉树中的深搜（典型算法思想）—— OJ例题算法解析思路

server/2025/2/27 8:23:46/

目录

一、2331. 计算布尔二叉树的值 - 力扣（LeetCode）

算法代码： 

代码思路概述

详细代码逻辑解释

节点定义

求值函数

基线条件

递归步骤

逻辑操作

总结

二、129. 求根节点到叶节点数字之和 - 力扣（LeetCode） 

算法代码： 

 代码思路概述

详细代码逻辑解释

节点定义

求和函数

深度优先搜索

递归累加

总结

三、814. 二叉树剪枝 - 力扣（LeetCode）

算法代码： 

代码思路概述

详细代码逻辑解释

节点定义

修剪函数

基线条件

递归修剪

节点修剪逻辑

返回结果

总结

四、98. 验证二叉搜索树 - 力扣（LeetCode）

算法代码：

代码思路概述

详细代码逻辑解释

节点定义

验证函数

基线条件

递归检查左子树

当前节点的验证

更新状态

递归检查右子树

总结

为什么要这样写？

五、230. 二叉搜索树中第 K 小的元素 - 力扣（LeetCode）

算法代码： 

代码思路概述

详细代码逻辑解释

节点定义

主函数

递归函数

总结

六、257. 二叉树的所有路径 - 力扣（LeetCode）

 算法代码：

代码思路概述

详细代码逻辑解释

节点定义

主函数

递归函数

总结

一、2331. 计算布尔二叉树的值 - 力扣（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:bool evaluateTree(TreeNode* root) {if (root->left == nullptr)return root->val == 0 ? false : true;bool left = evaluateTree(root->left);bool right = evaluateTree(root->right);return root->val == 2 ? left | right : left & right;}
};

代码思路概述

  1. 节点定义: 通过结构体 TreeNode 定义二叉树节点。

  2. 递归求值: 使用递归函数 evaluateTree 来评估布尔表达式的值。

  3. 基线条件: 当遇到叶子节点时，根据节点的值直接返回对应的布尔值。

  4. 递归步骤: 根据节点的值决定如何组合左右子树的布尔值。

详细代码逻辑解释

  1. 节点定义

    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) {}
};

    • TreeNode 结构体定义了二叉树节点，包含一个整型值 val 和指向左右子节点的指针 left 和 right。

    • 提供了多个构造函数，方便创建节点。

  2. 求值函数

    bool evaluateTree(TreeNode* root) {

    • evaluateTree 函数接收一个指向树根节点的指针 root，并返回对应的布尔值。

  3. 基线条件

    if (root->left == nullptr)return root->val == 0 ? false : true;

    • 如果当前节点是叶子节点（即没有左子节点），根据节点的值判断返回结果：

      • 如果值为 0，返回 false。

      • 如果值为 1，返回 true。

  4. 递归步骤

    bool left = evaluateTree(root->left);
bool right = evaluateTree(root->right);

    • 递归调用 evaluateTree 评估左子树和右子树，分别得到布尔值 left 和 right。

  5. 逻辑操作

    return root->val == 2 ? left | right : left & right;

    • 根据当前节点值决定如何组合左右子树的布尔值：

      • 如果节点值为 2（表示逻辑 OR），返回 left | right（即逻辑或操作）。

      • 如果节点值为 3（表示逻辑 AND），返回 left & right（即逻辑与操作）。

总结

  • 递归思路: 该算法通过递归遍历二叉树，将树结构转换为布尔表达式，逐步评估每个节点的值。通过结合左右子树的值实现最终的结果。

  • 时间复杂度: 时间复杂度为 (O(n))，其中 (n) 是树的节点数，因为每个节点都会被访问一次。

  • 空间复杂度: 空间复杂度为 (O(h))，其中 (h) 是树的高度，最坏情况下，对于一棵完全不平衡的树，空间复杂度为 (O(n))；而在平衡树中，空间复杂度为 (O(\log n))。

  • 应用场景: 此方法适用于需要根据树结构评估复杂布尔逻辑表达式的场景，如构建计算机逻辑、表达式求值等。

这段代码有效地展示了如何通过递归处理树结构的问题，体现了树的遍历和逻辑运算的结合。

二、129. 求根节点到叶节点数字之和 - 力扣（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 sumNumbers(TreeNode* root) { return dfs(root, 0); }int dfs(TreeNode* root, int presum) {presum = presum * 10 + root->val;if (root->left == nullptr && root->right == nullptr)return presum;int ret = 0;if (root->left)ret += dfs(root->left, presum);if (root->right)ret += dfs(root->right, presum);return ret;}
};

 代码思路概述

  1. 节点定义: 通过结构体 TreeNode 定义二叉树节点。

  2. 递归求和: 使用深度优先搜索（DFS）算法遍历二叉树，同时计算路径数字。

  3. 路径数字构建: 在递归过程中构建根到当前节点的路径数字。

  4. 返回结果: 当达到叶子节点时，返回当前路径数字，并在回溯阶段累加结果。

详细代码逻辑解释

  1. 节点定义

    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) {}
};

    • TreeNode 结构体定义了二叉树节点，包含一个整型值 val 和指向左右子节点的指针 left 和 right。

    • 提供了多个构造函数，方便创建节点。

  2. 求和函数

    int sumNumbers(TreeNode* root) { return dfs(root, 0); }

    • sumNumbers 函数接收一个指向树根节点的指针 root，并调用 dfs 函数进行深度优先搜索。初始的路径和为 0。

  3. 深度优先搜索

    int dfs(TreeNode* root, int presum) {presum = presum * 10 + root->val;if (root->left == nullptr && root->right == nullptr)return presum;

    • dfs 函数递归地遍历二叉树，接收当前节点的指针 root 和当前路径数字 presum。

    • 在每次递归调用时，更新 presum 为 presum * 10 + root->val，将当前节点的值连接到路径数字中。

    • 基线条件: 当达到叶子节点（即 root->left 和 root->right 都为空）时，返回当前路径数字 presum。

  4. 递归累加

    int ret = 0;
if (root->left)ret += dfs(root->left, presum);
if (root->right)ret += dfs(root->right, presum);
return ret;

    • 初始化一个变量 ret 用于存储当前节点的所有子树返回的数字总和。

    • 如果当前节点有左子树，递归计算左子树的路径和，并将结果累加到 ret 中。

    • 如果当前节点有右子树，递归计算右子树的路径和，并将结果累加。

    • 最后返回 ret，即当前节点的所有路径数字之和。

总结

  • 递归思路: 该算法通过深度优先搜索遍历二叉树，逐步构建从根到叶子的路径数字，并在达到叶子节点时返回对应的数字，最终将所有数字累加得到结果。

  • 时间复杂度: 时间复杂度为 (O(n))，其中 (n) 是树的节点数，因为每个节点都会被访问一次。

  • 空间复杂度: 空间复杂度为 (O(h))，其中 (h) 是树的高度，最坏情况下，对于一棵完全不平衡的树，空间复杂度为 (O(n))；而在平衡树中，空间复杂度为 (O(\log n))。

  • 应用场景: 该方法可以用于解决树形结构中涉及路径和的问题，如路径的字符串拼接和求和等。

这段代码有效展示了如何通过递归处理树结构的问题，体现了深度优先搜索的思想和路径累加的实现。

三、814. 二叉树剪枝 - 力扣（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* pruneTree(TreeNode* root) {if (root == nullptr)return nullptr;root->left = pruneTree(root->left);root->right = pruneTree(root->right);if (root->left == nullptr && root->right == nullptr && root->val == 0) {delete root; // 防⽌内泄漏root = nullptr;}return root;}
};

 

代码思路概述

  1. 节点定义: 通过结构体 TreeNode 定义二叉树节点。

  2. 递归修剪: 使用递归函数 pruneTree 来遍历树并修剪不需要的子树。

  3. 基线条件: 当遇到空节点时，返回空指针。

  4. 节点修剪: 在回溯过程中，检查当前节点及其子树，然后决定是否保留当前节点。

详细代码逻辑解释

 

  1. 节点定义

    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) {}
};

    • TreeNode 结构体定义了二叉树节点，包含一个整型值 val 和指向左右子节点的指针 left 和 right。

    • 提供了多个构造函数，方便创建节点。

  2. 修剪函数

    TreeNode* pruneTree(TreeNode* root) {

    • pruneTree 函数接收一个指向树根节点的指针 root，并返回修剪后的树的根节点。

  3. 基线条件

    if (root == nullptr)return nullptr;

    • 如果当前节点为空，直接返回空指针。这是递归的基线条件，表示已经到达树的叶子或无效节点。

  4. 递归修剪

    root->left = pruneTree(root->left);
root->right = pruneTree(root->right);

    • 递归调用 pruneTree 对当前节点的左子树和右子树进行修剪，更新当前节点的 left 和 right 指针。

  5. 节点修剪逻辑

    if (root->left == nullptr && root->right == nullptr && root->val == 0) {delete root; // 防止内存泄漏root = nullptr;
}

    • 检查当前节点的左右子节点是否都为空，并且当前节点的值是否为 0。

    • 如果条件满足，说明当前节点是一个不需要的节点，执行删除操作并将 root 指针设置为 nullptr，以避免内存泄漏。

  6. 返回结果

    return root;

    • 返回修剪后的树的根节点，这可能是原来的根节点，也可能是 nullptr（如果当前节点被删除）。

总结

  • 递归思路: 该算法通过递归遍历二叉树，逐步修剪不需要的子树，直到所有节点都被检查。通过回溯的方式实现了对树的重组和不需要部分的删除。

  • 时间复杂度: 时间复杂度为 (O(n))，其中 (n) 是树的节点数，因为每个节点都会被访问一次。

  • 空间复杂度: 空间复杂度为 (O(h))，其中 (h) 是树的高度。最坏情况下，对于一棵完全不平衡的树，空间复杂度为 (O(n))；而在平衡树中，空间复杂度为 (O(\log n))。

  • 应用场景: 此方法适用于需要修剪树结构或根据特定条件移除节点的场景，比如在图像处理、数据清理等领域。

这段代码有效展示了如何通过递归处理树结构的问题，体现了树的修剪和内存管理的重要性。

四、98. 验证二叉搜索树 - 力扣（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 {long prev = LONG_MIN;public:bool isValidBST(TreeNode* root) {if (root == nullptr)return true;bool left = isValidBST(root->left);// 剪枝if (left == false)return false;bool cur = false;if (root->val > prev)cur = true;// 剪枝if (cur == false)return false;prev = root->val;bool right = isValidBST(root->right);return left && right && cur;}
};

代码思路概述

  1. 节点定义: 通过结构体 TreeNode 定义二叉树节点。

  2. 中序遍历: 使用递归的方式进行中序遍历，同时检查节点值是否满足二叉搜索树的条件。

  3. 剪枝: 在遍历过程中，通过判断条件来剪枝，避免不必要的递归调用。

  4. 维护状态: 使用一个变量 prev 来跟踪上一个访问的节点值，以便进行比较。

详细代码逻辑解释

  1. 节点定义

    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) {}
};

    • TreeNode 结构体定义了二叉树的节点，包含一个整型值 val 和指向左右子节点的指针 left 和 right。

    • 提供了多个构造函数以便于创建节点。

  2. 验证函数

    bool isValidBST(TreeNode* root) {

    • isValidBST 函数接收一个指向树根节点的指针 root，并返回一个布尔值，表示该树是否是有效的二叉搜索树。

  3. 基线条件

    if (root == nullptr)return true;

    • 如果当前节点为空，直接返回 true。这是递归的基线条件，表示空树是有效的。

  4. 递归检查左子树

    bool left = isValidBST(root->left);
if (left == false)return false;

    • 递归调用 isValidBST 检查左子树的有效性，结果存储在 left 中。

    • 如果左子树不满足 BST 的条件，直接返回 false，进行剪枝。

  5. 当前节点的验证

    bool cur = false;
if (root->val > prev)cur = true;
if (cur == false)return false;

    • 检查当前节点的值是否大于 prev（上一个节点的值）。如果是，则 cur 被设置为 true。

    • 如果 cur 为 false，说明当前节点不满足 BST 的条件，直接返回 false。

  6. 更新状态

    prev = root->val;

    • 更新 prev 为当前节点的值，以便在检查右子树时使用。

  7. 递归检查右子树

    bool right = isValidBST(root->right);
return left && right && cur;

    • 递归调用 isValidBST 检查右子树的有效性，结果存储在 right 中。

    • 最后返回 left、right 和 cur 的与运算结果，只有当左子树、右子树和当前节点都满足条件时，才返回 true。

总结

  • 递归与状态维护: 该算法通过递归遍历二叉树，利用中序遍历的特性（BST 中序遍历结果是有序的）来检查树的结构，并通过 prev 变量维护上一个节点的值，实现有效的 BST 验证。

  • 时间复杂度: 时间复杂度为 (O(n))，其中 (n) 是树的节点数，因为每个节点都会被访问一次。

  • 空间复杂度: 空间复杂度为 (O(h))，其中 (h) 是树的高度。在最坏情况下（完全不平衡的树），空间复杂度为 (O(n))；而在平衡树中，空间复杂度为 (O(\log n))。

  • 应用场景: 该方法适用于需要验证树结构是否满足特定条件的场景，如二叉搜索树的验证等。

这段代码有效展示了如何通过递归和状态管理检查树形结构的特性，体现了二叉搜索树的基本概念和实现方式。

  1. prev 的作用：

    • prev 是一个全局变量，用于记录中序遍历过程中前一个访问的节点的值。

    • 在中序遍历中，访问顺序是左子树 -> 当前节点 -> 右子树。对于BST来说，中序遍历的结果应该是一个严格递增的序列。因此，prev 用于记录前一个节点的值，确保当前节点的值大于 prev。

  2. isValidBST 函数的逻辑：

    • 左子树的验证：bool left = isValidBST(root->left); 递归验证左子树是否是BST。

    • 剪枝操作：如果左子树不是BST，直接返回 false，不需要继续验证当前节点和右子树。

    • 当前节点的验证：bool cur = false; if (root->val > prev) cur = true; 检查当前节点的值是否大于 prev。如果是，则当前节点满足BST的条件。

    • 剪枝操作：如果当前节点不满足BST的条件，直接返回 false，不需要继续验证右子树。

    • 更新 prev：prev = root->val; 更新 prev 为当前节点的值，以便在验证右子树时使用。

    • 右子树的验证：bool right = isValidBST(root->right); 递归验证右子树是否是BST。

    • 返回结果：return left && right && cur; 只有当左子树、当前节点和右子树都满足BST条件时，才返回 true。

为什么要这样写？

  1. 中序遍历的思想：

    • 通过中序遍历，可以确保节点的值是严格递增的。prev 记录了前一个节点的值，确保当前节点的值大于前一个节点的值。

  2. 剪枝操作：

    • 剪枝是为了提高效率。如果在某个步骤中发现不满足BST的条件，就可以立即返回 false，而不需要继续递归下去。

  3. 全局变量 prev：

    • prev 是一个全局变量，用于在中序遍历过程中记录前一个节点的值。这样可以方便地比较当前节点的值是否大于前一个节点的值。

五、230. 二叉搜索树中第 K 小的元素 - 力扣（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 {int count;int ret;public:int kthSmallest(TreeNode* root, int k) {count = k;dfs(root);return ret;}void dfs(TreeNode* root) {if (root == nullptr || count == 0)return;dfs(root->left);count--;if (count == 0)ret = root->val;dfs(root->right);}
};

代码思路概述

  1. 节点定义: 通过结构体 TreeNode 定义二叉树节点。

  2. 变量初始化: 使用两个成员变量 count（用于计数）和 ret（用于存储结果）。

  3. 递归遍历: 使用 DFS 进行中序遍历，逐步找到第 k 小的元素。

  4. 剪枝: 在遍历过程中，当找到第 k 小的元素后，可以提前终止后续的遍历。

详细代码逻辑解释

  1. 节点定义

    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) {}
};

    • TreeNode 结构体定义了二叉树节点，包含一个整型值 val 和指向左右子节点的指针 left 和 right。

    • 提供了多个构造函数以便于创建节点。

  2. 主函数

    int kthSmallest(TreeNode* root, int k) {count = k; // 初始化计数器为 kdfs(root); // 开始深度优先搜索return ret; // 返回结果
}

    • kthSmallest 函数接收一个指向树根节点的指针 root 和一个整数 k，表示要查找第 k 小的元素。

    • 将 count 初始化为 k，并调用 dfs 函数进行遍历。

    • 最后返回 ret，即找到的第 k 小的元素。

  3. 递归函数

    void dfs(TreeNode* root) {if (root == nullptr || count == 0) // 基线条件return;dfs(root->left); // 先遍历左子树count--; // 访问当前节点，计数减一if (count == 0) // 如果已找到第 k 小元素ret = root->val; // 更新结果dfs(root->right); // 再遍历右子树
}

    • dfs 函数用于进行深度优先搜索，接收当前节点的指针 root。

    • 基线条件: 如果当前节点为空或者已经找到第 k 小的元素（count 为 0），则直接返回。

    • 递归访问左子树，先找到所有左子节点（这部分是在中序遍历中最小的节点）。

    • 访问当前节点，将 count 减一。

    • 如果 count 减到 0，说明当前节点就是第 k 小的元素，更新 ret 为当前节点的值。

    • 最后递归访问右子树。

总结

  • 中序遍历特性: 通过中序遍历，BST 的节点值会按升序排列，因此可以有效地找到第 k 小的元素。

  • 时间复杂度: 在最坏情况下，时间复杂度为 (O(n))，其中 (n) 是树的节点数，因为可能需要遍历所有节点。通常情况下，平均时间复杂度为 (O(k))。

  • 空间复杂度: 空间复杂度为 (O(h))，其中 (h) 是树的高度。在最坏情况下，对于完全不平衡的树，空间复杂度为 (O(n))；而在平衡树中，空间复杂度为 (O(\log n))。

  • 应用场景: 此方法适用于查找有序数据结构中的特定排名元素，如数据库查询、统计分析等。

这段代码有效展示了如何利用二叉搜索树的性质，通过递归遍历实现对第 k 小元素的查找，提供了一种优雅且高效的解决方案。

 

六、257. 二叉树的所有路径 - 力扣（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:vector<string> ret; // 记录结果vector<string> binaryTreePaths(TreeNode* root) {string path;if (root == nullptr)return ret;dfs(root, path);return ret;}void dfs(TreeNode* root, string path) {path += to_string(root->val);if (root->left == nullptr && root->right == nullptr) {ret.push_back(path);return;}path += "->";if (root->left)dfs(root->left, path);if (root->right)dfs(root->right, path);}
};

代码思路概述

  1. 节点定义: 通过结构体 TreeNode 定义二叉树节点。

  2. 结果存储: 使用一个向量 ret 来存储从根到叶子的所有路径。

  3. 深度优先搜索 (DFS): 使用递归函数 dfs 来遍历二叉树，构建路径字符串。

  4. 路径构建: 在遍历过程中，构建路径字符串，并在到达叶子节点时将路径加入结果中。

详细代码逻辑解释

  1. 节点定义

    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) {}
};

    • TreeNode 结构体定义了二叉树的节点，包含一个整型值 val 和指向其左右子节点的指针 left 和 right。

    • 提供了多个构造函数以便于创建节点。

  2. 主函数

    vector<string> binaryTreePaths(TreeNode* root) {string path;if (root == nullptr)return ret; // 如果树是空的，返回结果dfs(root, path); // 开始深度优先搜索return ret; // 返回所有路径
}

    • binaryTreePaths 函数接收一个指向树根节点的指针 root，并返回一个字符串向量，包含从根到所有叶子节点的路径。

    • 首先检查根节点是否为空，如果为空，直接返回结果向量 ret。

    • 调用 dfs 函数开始深度优先搜索。

  3. 递归函数

    void dfs(TreeNode* root, string path) {path += to_string(root->val); // 将当前节点的值添加到路径中if (root->left == nullptr && root->right == nullptr) {ret.push_back(path); // 如果到达叶子节点，保存路径return;}path += "->"; // 分隔符if (root->left)dfs(root->left, path); // 递归访问左子树if (root->right)dfs(root->right, path); // 递归访问右子树
}

    • dfs 函数用于深度优先搜索，接收当前节点的指针 root 和当前路径的字符串 path。

    • 构建路径: 首先将当前节点的值转换为字符串并添加到 path 中。

    • 检查叶子节点: 如果当前节点是叶子节点（即没有左子树和右子树），将当前路径添加到结果向量 ret 中。

    • 路径分隔符: 如果当前节点不是叶子节点，在路径后添加 "->" 作为分隔符，以便于连接后续节点的值。

    • 递归调用: 如果当前节点有左子节点，递归调用 dfs 访问左子树；如果有右子节点，则递归访问右子树。

总结

  • 深度优先搜索: 通过递归实现 DFS 遍历，构建从根到每个叶子节点的路径。

  • 时间复杂度: 时间复杂度为 (O(n))，其中 (n) 是树的节点数，因为每个节点都会被访问一次。

  • 空间复杂度: 空间复杂度为 (O(h))，其中 (h) 是树的高度。在最坏情况下（完全不平衡的树），空间复杂度为 (O(n))；而在平衡树中，空间复杂度为 (O(\log n))。

  • 应用场景: 此方法适用于需要记录路径的场景，如游戏中的移动路径、树结构的遍历以及路径分析等。 


http://www.ppmy.cn/server/170983.html

相关文章

2025中国经济白皮书赋能CES Asia，国际合作成新亮点

2025中国经济白皮书赋能CES Asia，国际合作成新亮点

近日&#xff0c;2025年中国经济白皮书的发布&#xff0c;为第七届亚洲消费电子技术贸易展&#xff08;CES Asia 2025&#xff09;的招商工作带来了重大利好消息&#xff0c;其在国际合作方面展现出的显著优势&#xff0c;成为吸引全球企业参与的重要因素。 白皮书重申了中国坚…
阅读更多...
将VsCode变得顺手好用（1

将VsCode变得顺手好用（1

目录 设置中文 配置调试功能 提效和增强相关插件 主题和图标相关插件 创建js文件 设置中文 打开【拓展】 输入【Chinese】 下载完成后重启Vs即可变为中文 配置调试功能 在随便一个位置新建一个文件夹&#xff0c;用于放置调试文件以及你未来写的代码&#xff0c;随便命名但…
阅读更多...
＜02.26＞Leetcode

＜02.26＞Leetcode

想想为什么要a走b的路b走a的路 因为这样到达相交点的话是同时的&#xff08;路程才是一样的&#xff09; 这样能保证第二圈就相遇了 如果各走各的路很难相遇 两个无交点的链表也有一个null交点 /*** Definition for singly-linked list.* public class ListNode {* int…
阅读更多...
为什么办公电脑需要使用企业级杀毒软件？--火绒企业版V2.0

为什么办公电脑需要使用企业级杀毒软件？--火绒企业版V2.0

首先&#xff0c;办公电脑处在一个网络连接和数据传输频繁的环境中&#xff0c;员工经常会接收和发送电子邮件、浏览网页、下载文件等&#xff0c;因此存在着各种网络安全威胁的风险。 其次&#xff0c;企业办公电脑作为业务运营的关键枢纽&#xff0c;存储着大量商业机密、客…
阅读更多...
本地部署阿里的万象2.1文生视频（Wan2.1-T2V-1.3B）模型

本地部署阿里的万象2.1文生视频（Wan2.1-T2V-1.3B）模型

文章目录 &#xff08;零&#xff09;在线体验&#xff08;一&#xff09;本地部署&#xff08;1.1&#xff09;克隆仓库&#xff08;1.2&#xff09;安装依赖&#xff08;1.2.1&#xff09;安装 flash-attention&#xff08;1.2.2&#xff09;重新安装依赖&#xff08;1.2.3&a…
阅读更多...
【找工作】C++和算法复习（自用）

【找工作】C++和算法复习（自用）

文章目录 C头文件自定义排序函数stl 算法数据结构树状数组 数学字符串manacherkmp 自用随便记录 C 排序 stl 头文件 全能头文件&#xff1a; #include<bits/stdc.h>自定义排序函数 bool compare(const int &odd1,const int &odd2) {return odd1>odd2; }…
阅读更多...
低代码在独具特色的业务中的应用：实践方案与未来展望

低代码在独具特色的业务中的应用：实践方案与未来展望

低代码开发是一种新兴的软件开发模式&#xff0c;它允许开发者通过图形化界面和最少的手写代码来快速构建应用程序。随着企业对快速开发和部署应用程序的需求日益增长&#xff0c;低代码平台在各个行业中得到了广泛的应用。本文将探讨低代码在独具特色的业务中的应用&#xff0…
阅读更多...
超过DeepSeek、o3，Claude发布全球首个混合推理模型，并将完成新一轮35亿美元融资...

超过DeepSeek、o3，Claude发布全球首个混合推理模型，并将完成新一轮35亿美元融资...

Anthropic于2025年2月25日发布全球首个“混合推理”AI模型Claude 3.7 Sonnet&#xff0c;并在融资层面取得重大进展&#xff0c;计划完成35亿美元的新一轮融资&#xff0c;估值将达615亿美元。以下是核心信息整理&#xff1a; 技术突破&#xff1a;双思维模型与代码能力 1. 混合…
阅读更多...
最新文章

Copyright @ 2022~2023