【二叉搜素树】——LeetCode二叉树问题集锦：6个实用题目和解题思路

解题思路：

• 这是一个二叉树的布尔评估问题。树的每个节点包含一个值，其中叶子节点值为 0 或 1，非叶子节点值为 2（表示 OR 操作）或 3（表示 AND 操作）。
  可以使用递归来评估布尔树：
  如果当前节点是叶子节点，直接返回其布尔值（0 为 False，1 为 True）。
  否则，递归评估左右子树。
  如果当前节点值为 2，返回左右子树的“或”运算结果；如果为 3，返回“与”运算结果。

class Solution 
{
public:
    bool evaluateTree(TreeNode* root) 
    {
        // 如果是叶节点，返回节点值的布尔结果
        if(root->left == nullptr) return root->val == 0 ? false : true;

        // 递归计算左子树的布尔值
        auto left = evaluateTree(root->left);
        // 递归计算右子树的布尔值
        auto right = evaluateTree(root->right);

        // 根据节点值来决定使用哪种布尔运算
        // 2 表示 OR 运算，3 表示 AND 运算
        return root->val == 2 ? left | right : left & right;    
    }
};

解题思路：

• 要计算从根节点到叶节点路径所表示的所有数字的总和。
  递归遍历每条路径，沿途维护一个当前的数字值，将每个节点的值添加到数字的末尾。
  如果到达叶子节点，将当前生成的数字添加到总和中。
  返回所有根到叶路径数字的总和。

class Solution 
{
public:
    // 主函数，调用辅助的深度优先搜索函数，初始累加和为0
    int sumNumbers(TreeNode* root) 
    {
        return dfs(root, 0);
    }

    // 深度优先搜索函数，用于计算从根到叶节点的路径和
    int dfs(TreeNode* root, int presum)
    {
        // 将当前节点的值加入路径值，乘以10以表示其位数
        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，就删除该子树。
  可以使用后序遍历递归判断每个节点的左右子树：
  先递归处理左子树和右子树。
  如果左子树没有 1，则将左子树置为 None；如果右子树没有 1，则将右子树置为 None。
  最后，判断当前节点是否为 1 或其子树是否包含 1，如果都没有，返回 None，否则返回当前节点。

class Solution 
{
public:
    // 主函数，调用递归函数修剪二叉树
    TreeNode* pruneTree(TreeNode* root) 
    {
        // 如果节点为空，直接返回空
        if (root == nullptr) return nullptr;

        // 递归处理左子树和右子树
        root->left = pruneTree(root->left);
        root->right = pruneTree(root->right);

        // 如果当前节点的值为0，且左右子树均为空，删除当前节点（设为nullptr）
        if (root->left == nullptr && root->right == nullptr && root->val == 0)
        {
            root = nullptr;
        }
        
        // 返回处理后的节点
        return root;
    }
};

解题思路：

• 验证二叉树是否为二叉搜索树（BST），即所有左子树节点值均小于当前节点，所有右子树节点值均大于当前节点。
  可以通过递归设定上下边界来验证每个节点：
  对于根节点，其值在 (−∞, +∞) 范围内。
  对于左子节点，设定其值范围为 (min, 当前节点值)。
  对于右子节点，设定其值范围为 (当前节点值, max)。
  如果所有节点都符合条件，则该树是 BST。

class Solution 
{
    long prev = LONG_MIN; // 用于记录前一个节点的值，初始为最小值
public:
    // 验证二叉搜索树的主函数
    bool isValidBST(TreeNode* root) 
    {
        // 如果节点为空，说明是合法的子树
        if (root == nullptr) return true;

        // 检查左子树是否为有效的二叉搜索树
        bool left = isValidBST(root->left);

        // 当前节点的有效性检查
        bool ret = false;
        if (root->val > prev) ret = true; // 当前节点值必须大于前一个节点值
        prev = root->val; // 更新前一个节点的值

        // 检查右子树是否为有效的二叉搜索树
        bool right = isValidBST(root->right);

        // 只有左子树、右子树都是有效BST，且当前节点符合条件时，返回true
        return left && right && ret; 
    }
};

解题思路：

• 由于 BST 的中序遍历会按从小到大的顺序输出节点值，因此可以通过中序遍历找到第 k 小的元素。
  进行中序遍历并计数，当计数达到 k 时，当前节点即为第 k 小的节点。
  优化：如果只找到第 k 小的节点后停止遍历，可以减少不必要的遍历。

class Solution 
{
    int count; // 记录剩余的步数，找到第 k 小的元素
    int ret;   // 用于存储第 k 小的元素值
public:
    // 主函数，初始化 count 并调用深度优先搜索
    int kthSmallest(TreeNode* root, int k) 
    {
        count = k;
        dfs(root);
        return ret;
    }

    // 中序遍历二叉搜索树的递归函数
    void dfs(TreeNode* root)
    {
        // 如果节点为空，直接返回
        if (root == nullptr) return;

        // 递归遍历左子树
        dfs(root->left);

        // 访问当前节点，更新 count
        count--;
        if (count == 0) ret = root->val; // 当 count 减到 0 时，找到第 k 小的元素

        // 递归遍历右子树
        dfs(root->right);
    }
};

解题思路：

• 需要找到二叉树中所有从根节点到叶节点的路径。
  通过 DFS（深度优先搜索）来遍历每一条路径，沿途构建路径字符串：
  如果当前节点是叶节点，将当前路径字符串加入结果列表。
  如果不是叶节点，继续递归其左右子树，构建路径字符串（添加 -> 以表示路径）。
  最终返回所有路径的字符串列表。

class Solution 
{
public:
    vector<string> ret; // 用于存储所有从根到叶节点的路径
    vector<string> binaryTreePaths(TreeNode* root) 
    {
        string path; // 当前路径字符串
        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);
    }
};