二叉树的深搜题解析

前言

大家好我是jiantaoyab，在这里分享给大家二叉树深搜相关题目的练习和解析，通过做题发现这树中的递归是非常好找的一般就是前序,中序，后序,为什么叫深搜呢?大家可以看看我第一篇

计算布尔二叉树的值

https://leetcode.cn/problems/evaluate-boolean-binary-tree/

class Solution {
public:
    bool evaluateTree(TreeNode* root) {
            //根节点返回val
            if(root->left == nullptr && root->right == nullptr) return root->val == 0 ? false : true;
            bool l = evaluateTree(root->left);
            bool r = evaluateTree(root->right);
            //知道 l 和 r 的值，返回 | / & 的结果
            return root->val == 2 ? l | r : l & r ;
    }
};
1
2
3
4
5
6
7
8
9
10
11

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

https://leetcode.cn/problems/3Etpl5/

解析

在 9 的这个位置下，只要算出它的左子树 和 右子树 的和就能够返回给上一层

递归的终止条件是到了叶子节点，此时返回presum就可以

代码

class Solution {
public:
    int PreOrder(TreeNode* root, int pre_sum)
    {
        //当前节点的上一个总和
        pre_sum = pre_sum * 10 + root->val;
        //到了叶子返回
        if(root->left == nullptr && root->right == nullptr) 
            return pre_sum;
        int ret = 0; //记录结果
        if(root->left)
        ret += PreOrder(root->left, pre_sum);
        if(root->right)
        ret += PreOrder(root->right, pre_sum);
        return ret;
    }
    int sumNumbers(TreeNode* root) {
        return PreOrder(root, 0);
    }
};


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

二叉树剪枝

https://leetcode.cn/problems/pOCWxh/

解析

分析这个例题，剪节点要通过后序遍历去操作

那什么时候执行剪呢？

当节点是根节点的且值是0的时候，返回nullptr

代码

class Solution {
public:
    TreeNode* pruneTree(TreeNode* root) {
        if(root == nullptr) return nullptr;
        if(root->left) root->left =  pruneTree( root->left);
        if(root->right) root->right =  pruneTree( root->right);
        if(root->val == 0 && root->left == nullptr && root->right == nullptr)
        {           
            root = nullptr;
        }
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

验证二叉搜索树

https://leetcode.cn/problems/validate-binary-search-tree/

解析

我们知道二叉树的中序遍历会把树排成有序的，但是开销的空间太大了，所以不用这种方法，

代码

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

        return left && right && cur;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

https://leetcode.cn/problems/kth-smallest-element-in-a-bst/

我们的中序遍历的结果就是升序的，所以题目问第k小的元素，只要用一个计数器等于k，计数器的结果等于0的时候就是第k小的元素

代码

class Solution {
    int count;
    int ret;
public:
    void LDR(TreeNode* root)
    {
        if(root == nullptr || count == 0) return;
        LDR(root->left);
        count--;
        if(count == 0) ret = root->val;
        LDR(root->right);
    }
    int kthSmallest(TreeNode* root, int k) {
       count = k;
       LDR(root);
       return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

二叉树的所有路径

https://leetcode.cn/problems/binary-tree-paths/

解析

代码

class Solution {
    vector<string> ret;
public:
    void dfs(TreeNode* root, string tmp)
    {
        //不管是不是叶子先放进去
        tmp += to_string(root->val);
        //是叶子了,放入ret
        if(root->left == nullptr && root->right == nullptr)
        {
            ret.push_back(tmp);
            return;
        }
        tmp += "->";
        //这里2个if包含了剪枝
        //就是如果左边或者右边没有的话,就不进去了
        if(root->left)  dfs(root->left, tmp);
        if(root->right) dfs(root->right, tmp);               
    }
    vector<string> binaryTreePaths(TreeNode* root) {
        if(root == nullptr) return ret;
        string tmp;
        dfs(root, tmp);
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27