目录1.计算布尔二叉树的值2.求根节点到叶子节点数字之和3.二叉树剪枝4.验证二叉搜索树5.二叉搜索树中第k小的数6.二叉树的所有路径1.计算布尔二叉树的值. - 力扣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; bool ret1 evaluateTree(root-left); bool ret2 evaluateTree(root-right); if(root-val 2)return ret1 || ret2; else return ret1 ret2; } };函数头你给我一个节点指针我告诉你返回的是true还是false函数体拿到两个子节点的返回值结合自己的val值返回。因为题意说是完整二叉树所以函数出口只需要判断该节点的left或者right里的一个为空即可返回。2.求根节点到叶子节点数字之和. - 力扣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 sumNumbers(TreeNode* root) { return mysumnumber(root, 0); } int mysumnumber(TreeNode* root,int prenum) { prenum prenum * 10 root-val; if(root-left nullptr root-right nullptr)return prenum; int ret 0; if(root-left)ret mysumnumber(root-left,prenum); if(root-right)ret mysumnumber(root-right,prenum); return ret; } };这道题题目中给定的函数头已经不足够我们使用所以我们要重新设计一个。每次计算到达一个节点时的值的时候需要用到上面节点的值所以我们提供一个prenum或者presum。第一个节点的prenum为0.我们以一个节点为例如果这个节点不为空第一步我们先求出这个节点的值并更新然后查看它是否有左右子节点如果都没有那就直接返回更新后的prenum。如果有左节点或者右节点那么经过判断之后用函数求得相应的值添加到ret中3.二叉树剪枝. - 力扣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; TreeNode* left pruneTree(root-left); TreeNode* right pruneTree(root-right); root-left left; root-right right; if(left nullptr right nullptr root-val 0)return nullptr; return root; } };按照常规依然是“相信”这个函数能帮我解决问题它的返回值是该root节点应该更新的左右节点。更新完左右节点后判断如果左右节点都为空且该节点为0那么返回空否则就返回root。本质上其实就是一个后序遍历出口是当root为空的时候。4.验证二叉搜索树. - 力扣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: long pre LONG_MIN; bool isValidBST(TreeNode* root) { if(root nullptr)return true; bool left isValidBST(root-left); bool cur false; if(pre root-val) { cur true; pre root-val; } bool right isValidBST(root-right); return left cur right; } };我们正常想的就是先判断左子树是不是二叉搜索树再看看当前节点是不是符合二叉搜索树定义最后看右子树符不符合二叉搜索树。判断的条件我们根据二叉搜索树的中序遍历的结果是一个有序的序列进行判断。这里我们再利用全局变量来减少传参避免过程过于复杂。因为该题里面节点内值的最小值为INT_MIN因此我们用long来声明这个全局变量pre。用LONG_MIN给它赋值因为无论如何中序遍历到达的第一个子节点必定是二叉搜索树。我们先判断左子树是否是二叉搜索树相信这个函数可以返回正确结果然后判断自己这个节点是否符合定义用自己的val与pre进行比较。最后判断右子树。判断完毕之后如果三者都符合二叉搜索树的定义那么就返回true否则返回false。如果我们要进行剪枝,只需要在接收完左子树的返回情况进行判断即可也可以继续在本节点判断的时候剪枝/** * 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: long pre LONG_MIN; bool isValidBST(TreeNode* root) { if(root nullptr)return true; bool left isValidBST(root-left); if(left false)return false; bool cur false; if(pre root-val) { cur true; pre root-val; } bool right isValidBST(root-right); return left cur right; } };5.二叉搜索树中第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 { public: int count; int ret; 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); } };这里我们还是需要借助全局变量简化代码。由题意我们知道一开始要找到最小的那个数必须不断进入左子树寻找然后再看本节点那么本质上就是一个中序遍历中序遍历每找到一个值就把count--。当count减到0时那么就找到了。我们还可以在出口处判断一下count如果等于0了也直接返回进行剪枝6.二叉树的所有路径. - 力扣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: vectorstring ret; vectorstring binaryTreePaths(TreeNode* root) { string path; btr(root,path); return ret; } void btr(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)btr(root-left,path); if(root-right)btr(root-right,path); } };这题我们主要是要意识到回溯里面的“恢复路径”path即为路径但是这题里面将path作为全局变量并不合适当返回上一层的时候必须尾删频繁的增删会使代码变得复杂。这里我们直接将其作为参数这样在返回上级的时候path依然是那个path。后面对root-left root-righ的判断一是为了防止空指针另一方面也是进行剪枝不需要进入节点后再判断