一、计算布尔二叉树的值
. - 力扣（LeetCode）
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:left&&right;
//直接return root->val==2?evaluateTree(root->left)||evaluateTree(root->right):evaluateTree(root->left)&&evaluateTree(root->right) 会导致递归的时间变长，因为我们没有去记住返回值，所以一旦需要就得重新递归回去计算
}
};二、求根节点到叶节点的数字之和
. - 力扣（LeetCode）
class Solution {
public:
int dfs(TreeNode* root,int presum)//presum也是为了回溯
{
if(root==nullptr) return 0;
presum=10*presum+root->val;//因为不管怎么样都得加
if(root->left==nullptr&&root->right==nullptr) return presum;
//此时如果左右不为空，加上这个结果
return dfs(root->left,presum)+dfs(root->right,presum);
}
int sumNumbers(TreeNode* root)
{
return dfs(root,0);
}
};三、二叉树剪枝
. - 力扣（LeetCode）
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;
return root;
}
};四、 验证二叉搜索树
. - 力扣（LeetCode）
class Solution {
public:
long prev=LONG_MIN;//比负无穷还小
bool isValidBST(TreeNode* root)
{
if(root==nullptr) return true;//为空的话是符合条件的
//进行中序遍历
bool l=isValidBST(root->left);//先找左子树
if(l==false) return false;//减枝（大多数的减枝就只是一个条件判断）
bool temp=(prev<root->val);//判断当前是否大于前驱
if(temp==false) return false;//减枝
prev=root->val;//更新前驱
bool r=isValidBST(root->right);//再找右子树
return r;
}
};五、二叉搜索树中第k小的节点
. - 力扣（LeetCode）
class Solution {
public:
int count=0;
int ret=0;
int kthSmallest(TreeNode* root, int k)
{
count=k;
dfs(root);
return ret;
}
void dfs(TreeNode* root)
{
if(root==nullptr) return;
dfs(root->left);
//中序遍历
if(--count==0) {ret=root->val; return;}//if判断也是剪枝
dfs(root->right);
}
};六、二叉树的所有路径
class Solution {
public:
vector<string> ret;//利用全局变量来存储我们返回的结果
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); //如果是叶子节点，返回最终结果
else //不是叶子节点的话，继续往后找
{
path+="->";
//继续去左右子树去找
dfs(root->left,path);
dfs(root->right,path);
}
}
vector<string> binaryTreePaths(TreeNode* root)
{
dfs(root,"");
return ret;
}
};七、路径总和2
. - 力扣（LeetCode）
思路1：全局path+回溯
class Solution {
public:
vector<vector<int>> ret;
vector<int> path;
vector<vector<int>> pathSum(TreeNode* root, int targetSum)
{
dfs(root,targetSum);
return ret;
}
void dfs(TreeNode* root,int targetSum)
{
if(root==nullptr) return;
//if(targetSum<0) return;有负数，所以不能剪枝
targetSum-=root->val;
path.push_back(root->val);
if(root->left==nullptr&&root->right==nullptr&&targetSum==0) {ret.push_back(path);return;}
dfs(root->left,targetSum);
if(root->left) path.pop_back();
dfs(root->right,targetSum);
if(root->right) path.pop_back();
}
};思路2：形参path记录路径结果
class Solution {
public:
vector<vector<int>> ret;
vector<vector<int>> pathSum(TreeNode* root, int targetSum)
{
dfs(root,targetSum,{});
return ret;
}
void dfs(TreeNode* root,int targetSum,vector<int> path)
{
if(root==nullptr) return;
targetSum-=root->val;
path.push_back(root->val);
if(root->left==nullptr&&root->right==nullptr&&targetSum==0) ret.push_back(path);
dfs(root->left,targetSum,path);
dfs(root->right,targetSum,path);
}
};八、从叶节点开始的最小字符串
. - 力扣（LeetCode）
思路1：全局path+回溯
class Solution {
public:
string minpath;
string path;
string smallestFromLeaf(TreeNode* root)
{
dfs(root);
return minpath;
}
void dfs(TreeNode* root)
{
if(root==nullptr) return;
//先加上对应的节点
path=char(root->val+'a')+path;
//如果是叶子节点，那么就和minpath进行比较，小的话更新
if(root->left==nullptr&&root->right==nullptr)//是叶子，就要进行比较
if(minpath.empty()||minpath>path) //为空的时候，也要更新
minpath=path;//更新
//没找到，就去左右子树找
dfs(root->left);
if(root->left) path.erase(path.begin());
dfs(root->right);
if(root->right) path.erase(path.begin());
}
};思路2：参数path记录路径结果
class Solution {
public:
string minpath;
string smallestFromLeaf(TreeNode* root)
{
dfs(root,"");
return minpath;
}
void dfs(TreeNode* root,string path)
{
if(root==nullptr) return;
//先加上对应的节点
path=char(root->val+'a')+path;
//如果是叶子节点，那么就和minpath进行比较，小的话更新
if(root->left==nullptr&&root->right==nullptr)//是叶子，就要进行比较
if(minpath.empty()||minpath>path) //为空的时候，也要更新
minpath=path;//更新
//没找到，就去左右子树找
dfs(root->left,path);
dfs(root->right,path);
}
};
