【递归、搜索与回溯算法】二叉树中的深搜

算法原理：

从宏观角度看问题：
我们从根节点看，想知道这一层最终的结果是什么，得先知道左子树是true还是false，右子树是true还是false。在知道两者后，再根据根节点自己的值进行与或运算。

递归函数流程：
(1) 当前问题规模为 n=1 时，即叶⼦节点，直接返回当前节点值；
(2) 递归求得左右⼦节点的值；
(3) 通过判断当前节点的逻辑运算符，计算左右⼦节点值运算得出的结果。

代码实现：

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

算法原理：

细节问题：

这里的递归出口是要在第一步执行完之后再判断，因为还要加上当前节点的值。

代码实现：

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

    int dfs(TreeNode* root, int prevsum)
    {
        prevsum = prevsum * 10 + root->val;
        // 递归出口
        if(root->left == nullptr && root->right == nullptr)
            return prevsum;
        // 函数体
        int ret = 0;
        if(root->left) ret += dfs(root->left, prevsum);
        if(root->right) ret += dfs(root->right, prevsum);
        return ret;
    }
};

算法原理：

我们可以采用后序遍历的方式来解决这个问题。在后序遍历中，我们先处理左⼦树，然后处理右⼦树，最后再处理当前节点。在处理当前节点时，我们可以判断其是否为叶⼦节点且其值是否为0，如果满⾜条件，我们可以删除当前节点。
算法流程：
1.递归出口：当传入节点为空时，不做任何处理；
2.递归处理左⼦树；
3.递归处理右⼦树；
4.处理当前节点：判断该节点是否为叶子节点(即左右子节点均被删除，当前节点成为叶子节点)，并且节点的值为 0：
a. 如果是，就删除掉；
b. 如果不是，就不做任何处理。

代码实现：

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; // 防止内存泄漏
            root = nullptr;
        }
        return root;
    }
};

算法原理：

根据"二叉搜索树的中序遍历是有序序列"这一特点入手。
我们可以定义一个全局变量，它的作用是：在中序遍历的过程中，保存上一个节点值，用于和下一个节点值进行比较。

在中序遍历的过程中也有两种策略：
策略1：递归中不用剪枝(有点暴力)
a. 左子树是二叉搜索树？
b. 当前结点符合二叉搜索树的定义？
c. 右子树也是二叉搜索树？
再根据这三者的结果，判断当前树是否满足，返回给上一层。
策略2：递归中用剪枝
当发现有一棵子树不是二叉搜索树时，那就不用再递归判断另一棵子树了，整颗树已经不满足了。

策略1代码实现：

class Solution 
{
    long prev = LONG_MIN;
public:
    bool isValidBST(TreeNode* root) 
    {
        // 思路：根据中序遍历
        if(root == nullptr) return true;
        
        // 判断左右子树
        bool left = isValidBST(root->left);
        
        // 判断当前节点
        bool cur = false;
        if(root->val > prev)
            cur = true;
        
        prev = root->val;
        bool right = isValidBST(root->right);
        
        return left && right && cur;
    }
};

策略2代码实现：

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

算法原理：

这道题也使用"二叉搜索树的中序遍历是有序序列"这一特点。
定义两个全局变量：
1是count用于计数：当count等于0时，当前节点值就是要返回的值。
2是ret用于存最终结果。

class Solution 
{
    int cnt; // 计数
    int ret; // 最终结果
public:
    int kthSmallest(TreeNode* root, int k) 
    {
        cnt = k;
        dfs(root);
        return ret;
    }

    void dfs(TreeNode* root)
    {
        // 递归出口+剪枝
        if(root == nullptr || cnt == 0) return;

        dfs(root->left);
        cnt--;
        if(cnt == 0) ret = root->val;
        dfs(root->right);
    }
};