centos做网站,建设一个房产网站赚钱吗,wordpress不同语言,清徐县建设局网站文章目录 1、求根节点到叶节点数字之和2、二叉树剪枝3、验证二叉搜索树4、二叉搜索树中第K小的元素5、二叉树的所有路径 1、求根节点到叶节点数字之和 给你一个二叉树的根节点 root #xff0c;树中每个节点都存放有一个 0 到 9 之间的数字。 每条从根节点到叶节点的路径都代表… 文章目录 1、求根节点到叶节点数字之和2、二叉树剪枝3、验证二叉搜索树4、二叉搜索树中第K小的元素5、二叉树的所有路径 1、求根节点到叶节点数字之和 给你一个二叉树的根节点 root 树中每个节点都存放有一个 0 到 9 之间的数字。 每条从根节点到叶节点的路径都代表一个数字 例如从根节点到叶节点的路径 1 - 2 - 3 表示数字 123 。 计算从根节点到叶节点生成的 所有数字之和 。 叶节点 是指没有子节点的节点。 class Solution {
public:int dfs(TreeNode* root,int presum){presumpresum*10root-val;if(root-leftnullptrroot-rightnullptr)return presum;int ret0;if(root-left) retdfs(root-left,presum);if(root-right) retdfs(root-right,presum);return ret;}int sumNumbers(TreeNode* root) {return dfs(root,0);}
};2、二叉树剪枝 给你二叉树的根结点 root 此外树的每个结点的值要么是 0 要么是 1 。 返回移除了所有不包含 1 的子树的原二叉树。 节点 node 的子树为 node 本身加上所有 node 的后代。 class Solution {
public:TreeNode* pruneTree(TreeNode* root) {if(rootnullptr)return nullptr;root-leftpruneTree(root-left);root-rightpruneTree(root-right);if(root-leftnullptrroot-rightnullptrroot-val0){delete root;//可加可不加return nullptr;}return root;}
};3、验证二叉搜索树 给你一个二叉树的根节点 root 判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下 节点的左子树 只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 class Solution {
public:long flagLONG_MIN;bool isValidBST(TreeNode* root) {if(rootnullptr)return true;bool leftisValidBST(root-left);if(leftfalse) return false;//剪枝作用为了提高效率bool curfalse;if(root-valflag){ curtrue;flagroot-val;}if(curfalse) return false;//剪枝bool rightisValidBST(root-right);return leftrightcur;}
};4、二叉搜索树中第K小的元素 给定一个二叉搜索树的根节点 root 和一个整数 k 请你设计一个算法查找其中第 k 个最小元素从 1 开始计数 class Solution {
public:int count0;int ret0;void dfs(TreeNode* root,int k){if(rootnullptr||countk)//count0是剪枝return ;dfs(root-left,k);count;if(countk)retroot-val;dfs(root-right,k);}int kthSmallest(TreeNode* root, int k) {dfs(root,k);return ret;}
};5、二叉树的所有路径 给你一个二叉树的根节点 root 按 任意顺序 返回所有从根节点到叶子节点的路径。 叶子节点 是指没有子节点的节点。 class Solution {
public:vectorstring dummy;void dfs(TreeNode* root,string str){strto_string(root-val);if(root-leftnullptrroot-rightnullptr){dummy.push_back(str);return;}str-;if(root-left) dfs(root-left,str);//dfs(root-left,str);之前的操作是没有判断不能只if(root-right) dfs(root-right,str);//判断root-leftnullptrroot-rightnullptr//还要想着单子树的问题已经好几次了}vectorstring binaryTreePaths(TreeNode* root) {dfs(root,);return dummy;}
};
