二叉搜索树中第 k 小的元素与二叉树的所有路径算法解析

二叉搜索树中第 k 小的元素与二叉树的所有路径算法解析 | 极客日志

10. 二叉搜索树中第 k 小的元素

题目链接：

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

题目描述：

文章配图

题目示例：

文章配图

解法：中序遍历 + 计数器剪枝

算法思路：

上述解法不仅使用大量额外空间存储数据，并且会将所有的结点都遍历一遍。但是，我们可以根据中序遍历的过程，只需扫描前 k 个结点即可。因此，我们可以创建一个全局的计数器 count，将其初始化为 k，每遍历一个节点就将 count--。直到某次递归的时候，count 的值等于 0，说明此时的结点就是我们要找的结果。

C++ 算法代码：

/**
 * 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 count, ret = 0;
    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);
        if(--count == 0) {
            ret = root->val;
            return;
        }
        dfs(root->right);
    }
};

算法总结及流程解析：

文章配图

11. 二叉树的所有路径

题目链接：

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

题目描述：

文章配图

题目示例：

文章配图

解法：回溯

算法思路：

使用深度优先遍历 (DFS) 求解。路径以字符串形式存储，从根节点开始遍历，每次遍历时将当前节点的值加入到路径中，如果该节点为叶子节点，将路径存储到结果中。否则，将 "->" 加入到路径中并递归遍历该节点的左右子树。

定义一个结果数组，进行递归。递归具体实现方法如下:

如果当前节点不为空，就将当前节点的值加入路径 path 中，否则直接返回；
判断当前节点是否为叶子节点，如果是，则将当前路径加入到所有路径的存储数组 path 中;
否则，将当前节点值加上 "->" 作为路径的分隔符，继续递归遍历当前节点的左右子节点；
返回结果数组。

特别地，我们可以只使用一个字符串存储每个状态的字符串，在递归回溯的过程中，需要将路径中的当前节点移除，以回到上一个节点。

C++ 算法代码：

/**
 * 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:
    // 用全局变量 ret 记录所有路径，全局不会受到递归回溯的影响
    vector<string> ret;
    vector<string> binaryTreePaths(TreeNode* root) {
        string path; // 用局部变量 path 记录路径的值，不用全局变量是为了便于回溯时'恢复原状'
        dfs(root, path);
        return ret;
    }
    void dfs(TreeNode* root, string path) {
        // 递归的结束条件：当前结点为空则结束递归进行返回
        if(root == nullptr) {
            return;
        }
        // 当遇到叶子结点时则不用再添加箭头，并且此时一条路径已经结束，
        // 用 string 数组 ret 进行记录并且直接返回
        if(root->left == nullptr && root->right== nullptr) {
            path += to_string(root->val);
            ret.push_back(path);
            return;
        }
        // 前序遍历
        path += to_string(root->val);
        path += "->";
        dfs(root->left, path);
        dfs(root->right, path);
    }
};

算法总结及流程解析：

文章配图

二叉搜索树中第 k 小的元素与二叉树的所有路径算法解析

10. 二叉搜索树中第 k 小的元素

题目链接：

题目描述：

题目示例：

解法：中序遍历 + 计数器剪枝

算法思路：

C++ 算法代码：

算法总结及流程解析：

11. 二叉树的所有路径

题目链接：

题目描述：

题目示例：

解法：回溯

算法思路：

C++ 算法代码：

算法总结及流程解析：

更多推荐文章

相关免费在线工具

二叉搜索树中第 k 小的元素与二叉树的所有路径算法解析

10. 二叉搜索树中第 k 小的元素

题目链接：

题目描述：

题目示例：

解法：中序遍历 + 计数器剪枝

算法思路：

C++ 算法代码：

算法总结及流程解析：

11. 二叉树的所有路径

题目链接：

题目描述：

题目示例：

解法：回溯

算法思路：

C++ 算法代码：

算法总结及流程解析：

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具