wordpress装多站点,wordpress调用指定文章分类链接,公司市场营销策划方案,此邀请码已被使用wordpress目录 计算布尔二叉树的值
求根节点到叶节点数字之和
二叉树剪枝
验证二叉搜索树
二叉搜索树中第K小的元素
二叉树的所有路径 计算布尔二叉树的值
题目 思路
这道题其实是比较简单的#xff0c;对二叉树来一次后序遍历即可#xff0c;当遇到叶子结点直接返回叶子节点中…
目录 计算布尔二叉树的值
求根节点到叶节点数字之和
二叉树剪枝
验证二叉搜索树
二叉搜索树中第K小的元素
二叉树的所有路径 计算布尔二叉树的值
题目 思路
这道题其实是比较简单的对二叉树来一次后序遍历即可当遇到叶子结点直接返回叶子节点中的bool值即可否则继续进行后序遍历返回得到的左子树和右子树的计算结果。
代码
class Solution {
public:bool evaluateTree(TreeNode* root) {if(root-leftnullptr) return root-val0?false:true;bool leftevaluateTree(root-left);bool rightevaluateTree(root-right);return root-val2?left|right:leftright;}
};
求根节点到叶节点数字之和
题目 思路
这道题所说的求根节点到叶节点数字之和并非是求根节点到叶节点所有数字直接相加起来而是将从根节点到叶节点路径上前一个位置的数字乘10该位置的值然后将所有从根节点到叶节点所有路径上的和相加起来。
直接来一次DFS即可如果当前节点没有左孩子和右孩子说明当前节点是叶节点直接返回前一个位置的数字乘10该位置的值即可否则DFS计算该节点左孩子那一侧得到的路径值以及该节点右孩子那一侧得到的路径值然后返回二者之和即可。
代码
class Solution {
public:int sumNumbers(TreeNode* root) {return dfs(root,0);}int dfs(TreeNode* root,int val){valval*10root-val;if(root-leftnullptr root-rightnullptr)return val;int ret0;if(root-left) retdfs(root-left,val);if(root-right) retdfs(root-right,val);return ret;}
};
二叉树剪枝
题目 思路
题目中的描述“返回溢出所有不包含1的子树的原二叉树”意思是剪掉不包含1的二叉树如何判定某个位置是否应该被剪掉来一次后序遍历即可即先判断该位置左子树是否不包含1以及该位置右子树是否不包含1如果该位置左右子树都不包含1且该位置的值是0那么就剪掉以该位置为根节点的子树当遇到节点值是空时直接返回空即可。
代码
class Solution {
public:TreeNode* pruneTree(TreeNode* root) {if(rootnullptr) return nullptr;root-leftpruneTree(root-left);root-rightpruneTree(root-right);if(root-leftnullptr root-rightnullptr root-val0)rootnullptr;return root;}
};
验证二叉搜索树
题目 思路
我们可能会想到对二叉树来一次中序遍历将中序遍历的结果存放到一个数组中然后判断数组是否是升序的因为对二叉搜索树进行中序遍历得到的结果是升序的但是这样有些浪费空间我们可以对二叉树进行中序遍历使用一个变量prev记录中序遍历的前一个位置的值每次到一个非空节点判断该节点是否大于中序遍历前一个位置的值如果大于继续进行中序遍历并更新prev的值为当前位置的值否则直接返回false。其中prev事先初始化为LONG_MIN因为这道题的节点值可能是INT_MIN。如果当前位置当前位置的左子树当前位置的右子树符合二叉搜索树的特点返回true。
代码
class Solution {long prevLONG_MIN;
public:bool isValidBST(TreeNode* root) {if(rootnullptr) return true;bool leftisValidBST(root-left);//剪枝if(leftfalse) return false;bool curfalse;if(root-val prev)curtrue;//剪枝if(curfalse) return false;prevroot-val;bool rightisValidBST(root-right);return left cur right;}
};
二叉搜索树中第K小的元素
题目 思路
我们可能会想到遍历二叉搜索树然后将所有节点的值添加到优先级队列中然后就能够找到二叉搜索树中第K小的元素了但是这样有些麻烦不妨利用二叉搜索树的性质对二叉树进行中序遍历使用一个变量来记录当前位置是位于中序遍历的第几个位置当正好是中序遍历的第K的位置那么该位置的值就是二叉搜索树中第K小的元素。
代码
class Solution {int count,ret;
public:int kthSmallest(TreeNode* root, int k) {countk;dfs(root);return ret;}void dfs(TreeNode* root){if(rootnullptr || count0) return;dfs(root-left);count--;if(count0) retroot-val;dfs(root-right);}
};
二叉树的所有路径
题目 思路
这道题还是比较简单的对二叉树进行一次DFS即可当处理到叶节点的时候直接返回得到的路径否则递归处理该位置左子树的路径以及该位置右子树的路径。
代码
class Solution {vectorstring ret;
public:vectorstring binaryTreePaths(TreeNode* root) {string path;dfs(root,path);return ret;}void dfs(TreeNode* root,string path){pathto_string(root-val);if(root-leftnullptr root-rightnullptr){ret.push_back(path);return;}path-;if(root-left) dfs(root-left,path);if(root-right) dfs(root-right,path);}
};
