dfs专题二 ——二叉树中的递归

key of 递归：

        完全相信子dfs一定可以完美解决问题

        只考虑一层问题

        全局变量 && 函数传参

        剪枝

1.计算布尔二叉树的值

link:2331. 计算布尔二叉树的值 - 力扣（LeetCode）

tip:后续遍历 

code

/*** 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) {return dfs(root);}bool dfs(TreeNode* root){if(root->val <= 1)  return root->val;bool ret1 = dfs(root->left), ret2 = dfs(root->right);if(root->val == 2) return ret1 || ret2;return ret1 && ret2;}
};

2.求根节点到叶子节点数字之和

link:129. 求根节点到叶节点数字之和 - 力扣（LeetCode）

tip:

        后序遍历

code1

/*** 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 dfs(root, 0);}long long dfs(TreeNode* root, long long preSum){if(!root) return 0;if(root->left == nullptr && root->right == nullptr) return preSum*10 + root->val;return dfs(root->left, preSum*10 + root->val) + dfs(root->right, preSum*10 + root->val);}
};

3.二叉树剪枝

link:814. 二叉树剪枝 - 力扣（LeetCode）

code

/*** 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) {return dfs(root);}TreeNode* dfs(TreeNode* root){if(!root) return nullptr;root->left = dfs(root->left);root->right = dfs(root->right);if(root->val == 0 && !root->left && !root->right) return nullptr;return root;}
};

4.验证二叉搜索树

link:98. 验证二叉搜索树 - 力扣（LeetCode）

key:         

        全局变量的使用

        剪枝

code

/*** 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 long pre = LLONG_MIN; // 全局变量bool flag = false;// 剪枝bool isValidBST(TreeNode* root) {// key:二叉搜索树 中序遍历 是升序的return dfs(root);// 中序遍历}bool dfs(TreeNode* root){if(flag) return false; // 剪枝放在第一位if(!root) return true;bool left = dfs(root->left);if(pre >= root->val) {flag = true;return false; // 剪枝}pre = root->val;bool right = dfs(root->right);return left && right;}};

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

link:230. 二叉搜索树中第 K 小的元素 - 力扣（LeetCode）

code

/*** 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 cnt; // 标记位int ret; // 全局变量int kthSmallest(TreeNode* root, int k) {cnt = k;dfs(root);return ret;}void dfs(TreeNode* root){if(!root || cnt == 0) return;// 剪枝dfs(root->left);cnt--;if(cnt == 0) ret = root->val;dfs(root->right);}
};

6.二叉树的所有路径

link:257. 二叉树的所有路径 - 力扣（LeetCode）

tip:

        使用全局变量， 可使空间复杂度为O（1)，但是回溯可能会比较麻烦， 需要手动回溯

        如果使用dfs参数代替全局变量，就不用手动回溯。但是空间复杂度会提高

code

/*** 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:vector<int> cur;vector<vector<int>> nums;vector<string> binaryTreePaths(TreeNode* root) {if(!root->left && !root->right) return {{char(root->val + '0')}};dfs(root);vector<string> ans;for(vector<int>& vc:nums){if(!vc.size()) continue;string tmp = to_string(vc[0]);for(int i = 1; i < vc.size(); i++){tmp += "->" + to_string(vc[i]);}ans.push_back(tmp);}return ans;}void dfs(TreeNode* root){// 出口if(!root) return;// 本轮操作cur.push_back(root->val);if(!root->left && !root->right){nums.push_back(cur);cur.pop_back();// 回溯return;}// 递归dfs(root->left);dfs(root->right);cur.pop_back();// 回溯}
};