【二叉搜素树】——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:// 主函数，调用辅助的深度优先搜索函数，初始累加和为0int 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，且当前节点符合条件时，返回truereturn left && right && ret; }
};

二叉搜索树中第K小的元素

解题思路：

• 由于 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);// 访问当前节点，更新 countcount--;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);}
};