调查问卷网站建设网站规划

计算布尔二叉树的值

题目链接

题解

宏观角度看待递归

1. 函数头：bool dfs(root)
2. 函数体：
bool left = dfs(root->left)
bool right = dfs(root->right)
左右的bool值再和根的值（| &）一下即为答案

细节看待递归
是一个二叉树的后序遍历：左右根

代码

/*** 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 l = evaluateTree(root->left);bool r = evaluateTree(root->right);return root->val == 2 ? l | r : l & r;}
};

求根节点到叶节点的数字之和

题目链接

题解

1. 函数头：dfs(root,persum)
需要一个值存从根节点往下的和
2. 函数体：
1、存根节点往下的和
2、左子树的和
3、右子树的和
4、左右子树的和相加返回给上一层
3. 递归出口：
在存根节点往下的和后，存完之后，如果左右子树为空就返回presum

代码

/*** 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 sum = 0;if(root->left) sum += dfs(root->left,presum);if(root->right) sum += dfs(root->right,presum);return sum;}int sumNumbers(TreeNode* root) {// 函数头return dfs(root,0);}
};

二叉树剪枝

题目链接

题解

1. 函数头：
TreeNode* dfs(root)
2. 函数体：
后序遍历，先处理左子树，再处理右子树，最后判断根是否为0
子问题：如果左子树为空，右子树为空，根的值是0，可以进行剪枝，然后返回空节点
3.递归的出口：
root == nullptr return nullptr
子问题可以做为题目的突破口

代码

/*** 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) {// 后序遍历// 只有把左子树看完,右子树看完是否都为0,并且根也要是0,才能把根节点删除// 子问题:左子树为空,右子树为空,根为0可以删除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;}
};

验证二叉搜索树

题目链接

题解

1. 二叉搜索树的中序遍历是一个有序的序列，这样全局变量可以帮我们判断这棵树是不是二叉搜索树了
2. 回溯：搜索到一条分支的终点后，再往回走，递归中往往涉及回溯
3. 剪枝：剪枝用来提高效率的，如果当前节点是false那么就可以直接返回了，不用去右树找了，这就是剪枝，如果左树是false也可以直接返回，也是剪枝
4. 这题利用中序遍历和一个全局变量和剪枝来完成，保证左右子树和根都是二叉搜索树

代码

class Solution 
{
long pre = LONG_MIN;
public:// 全部找完才能判断是不是二叉搜索树bool isValidBST(TreeNode* root) {// 怎么回溯后面的节点跟开始的根节点比较if(root == nullptr) return true;// 这句肯定错了,左树和右树如果是空,但是这个节点不符合二叉搜索树呢// if(root->left == nullptr && root->right == nullptr) return true;// 二叉搜索树的中序遍历一定是有序的// 必须保证左树和右树都是二叉搜索树// 左子树bool left = isValidBST(root->left);if(left == false) return false;// 剪枝// 当前节点bool cur = false;if(root->val > pre){cur = true;} if(cur == false) reurn false;// 剪枝pre = root->val;// 右子树bool right = isValidBST(root->right);return left && right && cur;}
};

二叉搜索树中第k小的元素

题目链接

题解

1. 使用一个全局变量来记录最终的结果 + 二叉搜索树的中序遍历 + 剪枝优化
2. count = k，每次中序遍历都减减，减到0就找到该数了，ret = root->val

代码

class Solution 
{
int ret = 0;
public:int dfs(TreeNode* root,int& count){// count == 0是在剪枝,等于0说明已经找到节点了if(root == nullptr || count == 0) return ret;dfs(root->left,count);count--;if(count == 0){ret = root->val;return ret;}dfs(root->right,count);return ret;}int kthSmallest(TreeNode* root, int k) {return dfs(root,k);}
};

二叉树的所有路径

题目链接

题解

1. 函数头：void dfs(root,string)
字符串用来每次存路径
2. 函数体：如果是叶子节点就把前面的路径加入到数组中，然后返回，如果是非叶子节点就递归左子树和右子树找出所有的路径
3. 递归出口：root == nullptr return;
4. 回溯：需要恢复现场，比如所有路径那题，如果是全局变量的string就需要恢复现场，避免后面的加入的数字影响前面的，叶子节点恢复现场是去掉数字，非叶子节点恢复现场是去掉数字和箭头，用全局的恢复现场比较麻烦，所以使用了传参的string，每次函数都是自动恢复现场，因为是局部的变量，每次string都是上次的模样
5.剪枝：上面这题就不需要再写root == nullptr的情况返回了，因为左右子树递归那里写了不等于空才去递归，相当于等于空的那部分递归剪掉了

代码

class Solution 
{
vector<string> ret;
public:void dfs(TreeNode* root,string path){// if(root == nullptr) return;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);// 回溯,如果不是全局变量的string,需要恢复现场if(root->right) dfs(root->right,path);}vector<string> binaryTreePaths(TreeNode* root) {string path;dfs(root,path);return ret;}
};

总结

1. 子问题是一个突破口
2. 要从宏观角度看待递归更加好做
3. 剪枝
4. 回溯
5. 从叶子节点看待问题更容易找到突破口
6. 画图更容易有思路