一、计算布尔二叉树的值
. - 力扣(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=(prevval);//判断当前是否大于前驱 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: vectorret;//利用全局变量来存储我们返回的结果 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 binaryTreePaths(TreeNode* root) { dfs(root,""); return ret; } };
七、路径总和2
. - 力扣(LeetCode)
思路1:全局path+回溯
class Solution { public: vector> ret; vector path; vector > 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> ret; vector > pathSum(TreeNode* root, int targetSum) { dfs(root,targetSum,{}); return ret; } void dfs(TreeNode* root,int targetSum,vector 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); } };