【递归、搜索与回溯】搜索

点赞收藏关注
你的支持是对我最大的鼓励，我们一起努力吧!

1.计算布尔二叉树的值

题目链接：2331. 计算布尔二叉树的值

题目分析：

给一颗完整二叉树，孩子节点要么是0要么是2，不存在1个孩子节点。
叶子节点和非叶子节点数字分别代表不同的意思，最后将root根结果bool值返回去。

算法原理：

解法：递归
宏观角度看待递归
当想知道root根节点bool值时，我要先知道左子树bool值，在知道右子树bool值，然后将左右子数的bool值和root本身信息做整合。当我们要知道左子树和右子树的bool值，你会发现它和大问题是一样的。大问题是解决整棵树的bool值，小问题是解决左子树bool值，右子树bool值。此时把左指针传给dfs，dfs把左子树bool值给你，把右指针传给dfs，dfs把右子树bool值给你。所以dfs非常好设计。
函数头
bool dfs(TreeNode* root)

函数体也就出来了，先求左子树bool值，在求右子树bool，不要管递归如何执行，只需要知道你给它数据它一定能完成任务。
bool left=dfs(root->left)
bool right=dfs(root->right)
最后在将左子树和右子树bool值和root做整合。

递归出口 到叶子节点就不需要往后递归了，此时返回结果就行了

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;
        
    }
};

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

题目链接：129. 求根节点到叶节点数字之和

题目分析：

将根到叶子节点组合的数加起来

算法原理：

解法：递归
首先我们要找到相同子问题，在树中相同子问题很好找，只需要关注递归到每一层需要干什么事情即可。当它们干的都是一样的事情，这就是相同的子问题。

当递归到5这一层，我发现要拿到和5相连下面的叶子节点的数把它们加起来，然后返回给根节点。当到5这一层

1. 首先要把12先给我传过来，不然我怎么算出1258，也就是到某一层要把它之前路径上之后给我传过来。然后拿到这个12，先算出125。
2. 然后把125传给左边
3. 把125传给右边
4. 然后把左边值的和与右边值的和相加，然后返回上一层节点

在这5这一层要完成4个任务，同理其他层也是要完成相同的任务。

1.函数头
首先要有一个返回值，就是传给dfs一个根节点把和它相连的叶子节点的和返回。但是要注意的是，我们除了要传一个根节点，还需要再把递归到该层的上面路径和拿到！ 因此函数头是int dfs(root，presum)

2.函数体
1、2、3、4个步骤

3.递归出口
当到叶子节点就可以返回了，但是要注意的是，这个递归出应该在步骤1之后的，因为到叶子节点也要把叶子节点的数加上才向上返回的。

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        
        return dfs(root,0);

    }

    int dfs(TreeNode* root,int presum)
    {
        presum=presum*10+root->val;

        if(root->left == nullptr && root->right == nullptr)
            return presum;
          
        int ret=0;
        if(root->left) ret+=dfs(root->left,presum);
        if(root->right) ret+=dfs(root->right,presum);

        return ret;

    }
};

3. 二叉树剪枝

题目链接：814. 二叉树剪枝

题目分析：

注意这里的剪枝和前面说的剪枝是不一样的，前面的是那条路不是通往终点的路不能在走了，这里的剪枝真的就是把分枝剪掉！

返回移除了所有 不包含 1 的子树 的原二叉树 的意思是，就是如果子树全是0就把它剪掉。如果子数既有1又有0就不能剪掉。

算法原理：

通过决策树，抽象出递归的三个核心问题
也就是说通过，完成二叉树剪枝这个任务，完成递归三个核心问题。
像之前先把每个子问题要完成任务先找到，但是有时候某些道题非常麻烦，无法总结出子问题到底干了什么问题，这道题是给一个根节点然后把子树全为0剪掉然后把新根节点返回来。但是有些题特别抽象你根本无法总结出来你让这个递归去完成什么任务，任务太多了。此时我们要有一个能力，通过研究递归的过程来总结出函数头、函数体、递归出口！

首先这肯定是一个后序遍历，先要确定左右子树是什么情况才能决定是否把这个子树干掉。

当作后序遍历到底最左节点，然后再后序发现它左为空右为空，然后自己本身也是0，说明可以给它剪枝。然后回到上一层但是有一个问题，是不是要修改上一层左子树的指针啊，因此这个递归函数要有一个返回值 TreeeNode*。

然后如果左右子树都为空，但自己是1，说明不能剪枝

当我们把根左子树都弄好了，其实整个递归过程就出来。

1. 函数头
   TreeNode* dfs(root) 给一个根节点，然后把结果给我
2. 函数体
   左子树右子树都搞完返回给我一个东西，然后通过返回值在结合我自己看是否需要把自己删除。
   1.左子树、2.右子树、 3.判断
3. 递归出口
   遇到null结束，就返回null

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)
            return nullptr;
        else 
            return root;
        
    }
};

4.验证二叉搜索树

题目链接：98. 验证二叉搜索树

题目描述：

算法原理：
这道题主要想说的有三个方面 1. 全局变量的优势 ，2. 回溯 ，3. 剪枝

这里我们利用一个性质，二叉搜索树的中序遍历结果，是一个有序的序列
可能你会想到用一个数组记录中序遍历的结果，然后在遍历一下数组。但是这样空间开销太大了。

我们还是利用这个性质解决这个问题，但是我们可以仅用一个全局变量就来判断这个中序遍历是否是有序的。这个全局变量是在中序遍历中当我遍历到某一个位置它的前序是多少。 并且因为是全局的，并不需要考虑在递归中如何传递，直接拿过来用就可以了！

当中序遍历到第一个节点后，比较该值和prev的大小，当前这个值比无穷小大说明当前中序遍历是有序的，就更新prev等于这个值。然后向上传，同理依旧是拿这个值和prev做比较等等，知道中序遍历到19发现这个值比prev要小，此时中序遍历就不是有序的，说明30左子树就不一颗二叉搜索树，也说明20右子树不是一颗二叉搜索树，进而说明整棵树就不是一颗二叉搜索树。直接返回即可！

所以这道题我们可以借助全局变量和中序遍历就可以解决这个问题。
我们有两种策略判断它是否是一个二叉树。
策略一：

1. 左子树是一颗二叉搜索树，
2. 当前节点也要符合二叉搜索树的定义
3. 右子树也是一颗二叉搜索树

此时就颗树就是一颗二叉搜索树！

一个递归99%都有回溯，往上层返回就是回溯！

当前节点值的范围正好有INT_MIN，如果我们prev=INT_MIN 有可能第一层判断就有问题。因此把prev类型换一下，long 或者 long long

class Solution {
public:
    long prev=LONG_MIN;
    bool isValidBST(TreeNode* root) {

        if(root == nullptr) return true;

        bool left=isValidBST(root->left);
        bool cur=false;
        if(root->val > prev)
        {
            prev=root->val;
            cur=true;
        }
        bool right=isValidBST(root->right);

        return left && cur && right;
    }
};

策略二：剪枝

当判断某棵子树不是二叉搜索树，整体就已经不是二叉搜索树了，就没有必要在去其他子树递归了，直接返回结果就行了。加快了我们的搜索过程

剪枝其实很简单，不要想的那么复杂。

class Solution {
public:
    long prev=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(root->val > prev)
        {
            prev=root->val;
            cur=true;
        }
        //剪枝
        if(cur == false) return false;
        bool right=isValidBST(root->right);

        return left && cur && right;
    }
};

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

题目链接：230. 二叉搜索树中第K小的元素

题目描述：

算法原理：

有了上面题的基础，这道题就非常简单了，仅需两个全局变量+中序遍历就行了

每次count-1，直到count==0，用ret记录结果。找到最终结果此时其他子树也不用遍历。也可以使用剪枝。

如果不使用全局遍历，就需要在递归函数中传参，并且还需要考虑参数在递归函数中如何改变。

class Solution {
    int count=0,ret=0;
public:
    int kthSmallest(TreeNode* root, int k) {

        count=k;
        dfs(root);
        return ret;
        // if(root == nullptr) return 0;

        // if(count <= k)
        //     kthSmallest(root->left,k);
        // ++count;
        // if(count == k)
        // {
        //     ret=root->val;
        // }
        // if (count <= k)
        //     kthSmallest(root->right,k);
        // 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);
    }
};

6.二叉树的所有路径

题目链接：257. 二叉树的所有路径

题目分析：

题目很简单，让找根到叶子节点的所有路径。

算法原理：
这道题重点强调的还是

1. 全局变量
2. 回溯
3. 剪枝

其中这道题最重要的是想说回溯 ----> “恢复现场” ，一定纠正思想 因为出现了回溯 才会想到要 恢复现场

只要出现递归必定会有回溯，既然回溯中有恢复现场，那就可以这样说，只要有深度优先遍历就有恢复现场的操作。只不过在简单题恢复现场这个动作并不明显，因为参数在递归过程中就已经自动恢复现场了，但是在一些难的题里面，一旦用到全局变量，我们要手动恢复，这个恢复现场操作就会变成额外重要。

比如这道题我们用两个全局变量，path是把根到叶子节点所经历的路径记录下来，ret是把path到叶子节点后的整条路径记录下来。

path遇到不是叶子节点就 值 + ->，遇到叶子就把path放到ret数组中。但是此时有一个超级致命的问题，回溯的时候，path要回到上一层，你会发现回溯到上一层path不应该有 4 的，因为path往其他子树传仅需要传 1->2-> 就行了！那此时就应该 恢复现场，把全局变量恢复下去之前的样子。此时还有一个问题如果把path设计成全局变量，回溯时path要不停pop，从叶子节点回溯还好说，但是从非叶子节点回溯要pop两次，挺麻烦的！

这道题用全局变量path记录路径比较麻烦，仅是这道题全局path不好用，但是比较麻烦的题全局path好用，这里只是为了说明，有恢复现场这个操作的。

这道题我们函数头这样设计 void dfs(root,path)，把path当成参数传给函数，你会发现恢复现场特别容易，函数特性就已经帮我们恢复现场了。因为每次函数都会重新创建一个path，回溯到上一层用的还是上一层自己的path。就不用自己手动恢复了。

总结一下：全局变量 不好手动 恢复现场，那就 参数 自动 恢复现场

函数头，函数体都差不多了，接下来就是递归出口了，当root == nullptr 返回。但是这里递归还要进去才返回。此时我们可以剪枝，当非空进去，空就不要进！

class Solution {
    vector<string> ret;
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        string path;
        dfs(root,path);
        return 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);
            return;
        }

        path+="->";
        // dfs(root->left,path);
        // dfs(root->right,path);

        //回溯+剪枝 if就是剪枝
        if(root->left) dfs(root->left,path);

        //中间如果有就是回溯

        if(root->right) dfs(root ->right,path);
    }
};