《算法集训传送门》

  👉引言

---

💖 ❄️我们的算法之路❄️💖

   众所周知，作为一名合格的程序员，算法 能力 是不可获缺的，并且在算法学习的过程中我们总是能感受到算法的✨魅力✨。
              ☀️🌟短短几行代码，凝聚无数前人智慧；一个普通循环，即是解题之眼🌟☀️
   💝二分，💝贪心，💝并查集，💝二叉树，💝图论，💝深度优先搜索(dfs)，💝宽度优先搜索（bfs），💝数论，💝动态规划等等， 路漫漫其修远兮，吾将上下而求索！ 希望在此集训中与大家共同进步，有所收获！！！🎉🎉🎉

---

今日主题：二叉搜索树

---

 👉⭐️第一题💎

   ✨题目

      938. 二叉搜索树的范围

深度优先搜索，由于是二叉搜索树，层次结构是 左节点小于 根节点，右节点大于根节点，根据这个特性，就可以推出：

• 当 节点为Null时，直接返回0（无影响）

• 当 root节点 值在 L，R之间（包含端点）时，返回left tree与right tree 的和 再加上 当前root节点的value值

• 当root 的value 大于 R时，右子树都是递增的，所以只需要返回左子树的和即可

• 同样的，当 root的value小于L时，return right tree

   ✨代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int rangeSumBST(TreeNode root, int L, int R) {
        if (root == null) {
            return 0;
        }
        if (root.val < L) {
            return rangeSumBST(root.right, L, R);
        }
        if (root.val > R) {
            return rangeSumBST(root.left, L, R);
        }
        return root.val + rangeSumBST(root.left, L, R) + rangeSumBST(root.right, L, R);
    }
}


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

 👉⭐️第二题💎

   ✨题目

      剑指 Offer 26. 树的子结构

首先判断是否 B是否是 A的子结构，也就是说 能不能在A中找到B（与B一样的树形结构以及节点值），怎么下手呢？

• 首先，子结构的根节点一定是A的子节点，所以需要先序遍历，也就是深度优先搜索
• 然后 搜索每个子节点，以此节点为根节点去寻找是否包含B

使用isSubStructure（）函数去 先序遍历A的子节点，recur（）判断以当前节点为根节点的A子结构是否包含B（与B同步搜索，如果发现两者不一致，则说明不包含）

   ✨代码：

class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        def recur(A, B):
            if not B: return True
            if not A or A.val != B.val: return False
            return recur(A.left, B.left) and recur(A.right, B.right)

        return bool(A and B) and (recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))

1
2
3
4
5
6
7
8
9

---

🌹写在最后💖：
相信大家对今天的集训内容的理解与以往已经有很大不同了吧，或许也感受到了算法的魅力,当然这是一定的，路漫漫其修远兮，吾将上下而求索！伙伴们，明天见！🌹🌹🌹