✨✨✨学习的道路很枯燥，希望我们能并肩走下来!
文章目录
目录
文章目录
前言
一. 深搜的总结
二. 二叉树的深搜题目
2.1 计算布尔二叉树的值
2.2 求根节点到叶节点的数字之和
2.3 二叉树剪枝
2.4 验证二叉搜索树
2.5 二叉搜索树中第k小的节点
2.6 二叉树的所有路径
总
前言
本篇详细介绍了二叉树中的深搜，让使用者了解二叉树中的深搜，而不是仅仅停留在表面， 文章可能出现错误，如有请在评论区指正，让我们一起交流，共同进步！
一. 深搜的总结
二. 二叉树的深搜题目
2.1 计算布尔二叉树的值
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;}
};2.2 求根节点到叶节点的数字之和
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 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;}int sumNumbers(TreeNode* root) {return dfs(root,0);}
};2.3 二叉树剪枝
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;}
};2.4 验证二叉搜索树
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);bool cur = false; //判断当前位置if(root->val > prev)cur = true;prev = root->val;bool right = isValidBST(root->right);return left && right && cur;}
};剪枝：
/*** 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;}
};2.5 二叉搜索树中第k小的节点
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);}
};2.6 二叉树的所有路径
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 {vector<string> ret;string path;
public:vector<string> binaryTreePaths(TreeNode* root) {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);}
};总结
✨✨✨各位读友，本篇分享到内容是否更好的让你理解二叉树深搜，如果对你有帮助给个👍赞鼓励一下吧！！
🎉🎉🎉世上没有绝望的处境，只有对处境绝望的人。
感谢每一位一起走到这的伙伴，我们可以一起交流进步！！！一起加油吧！！