当前位置：首页 > news >正文

DFS：二叉树中的深搜

news 2024/9/26 3:29:21

✨✨✨学习的道路很枯燥，希望我们能并肩走下来!

文章目录

前言

一. 深搜的总结

二. 二叉树的深搜题目

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