南城网站建设公司信息,网站尺寸规范,wordpress wending,重庆市建设工程信息网资质系统递归的本质是找重复的子问题 文章目录 1.计算布尔二叉树的值2.从根节点到叶节点数字之和3.二叉树剪枝4.验证二叉搜索树5.二叉搜索树中第K小的元素6.二叉树的所有路径 1.计算布尔二叉树的值
计算布尔二叉树的值
class Solution {
public:bool evaluateTree(TreeNode* root) …递归的本质是找重复的子问题 文章目录 1.计算布尔二叉树的值2.从根节点到叶节点数字之和3.二叉树剪枝4.验证二叉搜索树5.二叉搜索树中第K小的元素6.二叉树的所有路径 1.计算布尔二叉树的值
计算布尔二叉树的值
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:leftright; }
};2.从根节点到叶节点数字之和
从根节点到叶节点数字之和
class Solution {
public:int sumNumbers(TreeNode* root) {return dfs(root,0);}int dfs(TreeNode* root,int prevsum){prevsum prevsum*10root-val;if(root-left nullptr root-right nullptr) return prevsum;int ret 0;if(root-left) ret dfs(root-left,prevsum);if(root-right) ret dfs(root-right,prevsum);return ret;}
};3.二叉树剪枝
二叉树剪枝
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;//防止内存泄漏前提是节点是new出来的root nullptr;}return root;}
};4.验证二叉搜索树
验证二叉搜索树
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-valprev){cur true;}if(cur false) return false;prev root-val;bool right isValidBST(root-right);return left right cur;}
};5.二叉搜索树中第K小的元素
二叉搜索树中第K小的元素
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);}
};6.二叉树的所有路径
二叉树的所有路径
class Solution {vectorstring ret;
public://递归回溯vectorstring binaryTreePaths(TreeNode* root) {string path;dfs(root,path);return ret;}void dfs(TreeNode* root,string path){path pathto_string(root-val);if(root-left nullptr root-right nullptr){ret.push_back(path);}path -;if(root-left) dfs(root-left,path);if(root-right) dfs(root-right,path);}
};有什么不懂的可以后台直接私信我嗷
