【递归、回溯和剪枝】二叉树中的深搜_二叉树剪枝和回溯

⼆叉树中的深搜
深度优先遍历（DFS，全称为 Depth First Traversal），是我们树或者图这样的数据结构中常⽤的⼀种遍历算法。这个算法会尽可能深的搜索树或者图的分⽀，直到⼀条路径上的所有节点都被遍历完毕，然后再回溯到上⼀层，继续找⼀条路遍历。
在⼆叉树中，常⻅的深度优先遍历为：前序遍历、中序遍历以及后序遍历。
因为树的定义本⾝就是递归定义，因此采⽤递归的⽅法去实现树的三种遍历不仅容易理解⽽且代码很简洁。并且前中后序三种遍历的唯⼀区别就是访问根节点的时机不同，在做题的时候，选择⼀个适当的遍历顺序，对于算法的理解是⾮常有帮助的。

1.计算布尔二叉树的值 

计算布尔二叉树的值 

 思路：

/**
 * 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) {
        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.求根节点到叶子节点数字之和

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

思路：

/**
 * 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);        
    }
    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.二叉树剪枝

二叉树剪枝

思路：

/**
 * 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) {
        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;
    }
};

4.验证二叉搜索树

验证二叉搜索树

思路：

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

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

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

思路：

注意全局变量的妙用

/**
 * 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 count;
    int ret;
    int kthSmallest(TreeNode* root, int k) {
        count = k;
        dfs(root);
        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.二叉树的所有路径

二叉树的所有路径

思路：

path的妙用，把path放在参数列表，可以方便回溯，不需要我们手动进行回溯了。

/**
 * 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<string> ret;
    vector<string> binaryTreePaths(TreeNode* root) {
        string path;
        if(root == nullptr) return ret;
        dfs(root, path);
        return ret;
    }
    void dfs(TreeNode* root, string path)
    {
        path += to_string(root->val);
        if(root->left == nullptr && root->right == nullptr)
        {
            ret.push_back(path);
            return;
        }
        path += "->";
        if(root->left) dfs(root->left, path);
        if(root->right) dfs(root->right, path);
    }
};