💖 ❄️我们的算法之路❄️💖
众所周知，作为一名合格的程序员，算法 能力 是不可获缺的，并且在算法学习的过程中我们总是能感受到算法的✨魅力✨。
☀️🌟短短几行代码，凝聚无数前人智慧；一个普通循环，即是解题之眼🌟☀️
💝二分，💝贪心，💝并查集，💝二叉树，💝图论，💝深度优先搜索(dfs) ，💝宽度优先搜索（bfs） ，💝数论，💝动态规划等等， 路漫漫其修远兮，吾将上下而求索！ 希望在此集训中与大家共同进步，有所收获！！！🎉🎉🎉
今日主题：二叉搜索树
👉⭐️第一题💎
✨题目
深度优先搜索，由于是二叉搜索树，层次结构是 左节点小于 根节点，右节点大于根节点，根据这个特性，就可以推出：
- 当 节点为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); } }
👉⭐️第二题💎
✨题目
首先判断是否 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))
🌹写在最后💖：
相信大家对今天的集训内容的理解与以往已经有很大不同了吧，或许也感受到了算法的魅力,当然这是一定的，路漫漫其修远兮，吾将上下而求索！伙伴们，明天见！🌹🌹🌹
