树
下面是关于树及其相关概念的详细介绍：
树的基本概念
树 (Tree) 是一种数据结构，由节点 (Node) 组成，具有以下特点：
树中的每个节点有零个或多个子节点。
没有父节点的节点称为根节点 (Root)。
每个非根节点有且只有一个父节点。
除根节点外，每个节点可以有零个或多个子节点。
树中没有环路。
树的相关术语
1. 节点 (Node)：树的基本单位，每个节点包含一个值和若干子节点的引用。
2. 根节点 (Root)：树的顶端节点，没有父节点。
3. 子节点 (Child)：一个节点的直接下属节点。
4. 父节点 (Parent)：拥有一个或多个子节点的节点。
5. 叶节点 (Leaf)：没有子节点的节点。
6. 内部节点 (Internal Node)：至少有一个子节点的节点。
7. 兄弟节点 (Sibling)：具有相同父节点的节点。
8. 路径 (Path)：从一个节点到另一个节点的节点序列。
9. 深度 (Depth)：节点到根节点的路径长度（边的数量）。
10. 高度 (Height)：节点到叶节点的最长路径长度。
11. 层次 (Level)：树中节点的深度。
12. 子树 (Subtree)：由某个节点及其所有后代节点组成的树。
特殊类型的树
1. 二叉树 (Binary Tree)：每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树及有关内容将会在下面讲述。
2. 二叉搜索树 (Binary Search Tree, BST)：一种二叉树，具有以下性质：
对于每个节点，其左子树中的所有节点的值都小于该节点的值。
其右子树中的所有节点的值都大于该节点的值。
3. 平衡树 (Balanced Tree)：树的高度保持在对数级别，以确保高效的操作。
4. 红黑树 (Red-Black Tree)：一种自平衡二叉搜索树，具有红黑性质，保证最坏情况下的操作时间复杂度为O(\log n)。
5. AVL树 (AVL Tree)：另一种自平衡二叉搜索树，通过严格的平衡条件（左右子树高度差不超过1）来保持平衡。
6. B树 (B-Tree)：一种广泛用于数据库和文件系统的自平衡多路搜索树。
7. B+树 (B+ Tree)：B树的变种，所有值都存储在叶子节点，内部节点只存储键。
以上搜索树的有关内容会在未来的二叉搜索树中讲述。
树的遍历
树的遍历是指按照某种顺序访问树中的所有节点，常见的遍历方法有：
1. 前序遍历 (Pre-order Traversal)：先访问根节点，再访问左子树，最后访问右子树。
2. 中序遍历 (In-order Traversal)：先访问左子树，再访问根节点，最后访问右子树。
对于二叉搜索树，中序遍历会产生有序序列。
3. 后序遍历 (Post-order Traversal)：先访问左子树，再访问右子树，最后访问根节点。
4. 层次遍历 (Level-order Traversal)：按层次从上到下、从左到右访问节点，通常使用队列实现。
二叉树
二叉树的基本概念
二叉树 (Binary Tree) 是一种树形数据结构，其中每个节点最多有两个子节点，分别称为左子节点 (Left Child) 和右子节点 (Right Child)。
二叉树的类型
1. 满二叉树 (Full Binary Tree)：
每个节点要么是叶节点，要么有两个子节点。
叶节点都在同一层。
2. 完全二叉树 (Complete Binary Tree)：
除了最后一层，所有层都是满的。
最后一层的叶节点尽可能地向左排列。
3. 平衡二叉树 (Balanced Binary Tree)：
平衡二叉树是指该树所有节点的左右子树的深度相差不超过 1。
树的高度保持在对数级别，以确保高效的操作。
例如，AVL树和红黑树都是平衡二叉树的例子。
4. 二叉搜索树 (Binary Search Tree, BST)：
对于每个节点，其左子树中的所有节点的值都小于该节点的值，其右子树中的所有节点的值都大于该节点的值。
二叉树的遍历方法
1. 前序遍历 (Pre-order Traversal)：
访问顺序：根节点 -> 左子树 -> 右子树。
递归实现：
def preorder(node):
if node:
print(node.value) # Do something
preorder(node.left)
preorder(node.right)2. 中序遍历 (In-order Traversal)：
访问顺序：左子树 -> 根节点 -> 右子树。
对于二叉搜索树，中序遍历会产生有序序列。
递归实现：
def inorder(node):
if node:
inorder(node.left)
print(node.value) # Do something
inorder(node.right)3. 后序遍历 (Post-order Traversal)：
访问顺序：左子树 -> 右子树 -> 根节点。
递归实现：
def postorder(node):
if node:
postorder(node.left)
postorder(node.right)
print(node.value) # Do something4. 层次遍历 (Level-order Traversal)：
按层次从上到下、从左到右访问节点。
通常使用队列实现：
from collections import deque
def level_order(root):
if not root:
return
queue = deque([root]) # 队列的思想
while queue:
node = queue.popleft()
print(node.value)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)二叉树的性质
1. 节点数：对于高度为h 的二叉树，最少有h+1 个节点，最多有2^{h+1} - 1 个节点。
2. 高度：对于n 个节点的二叉树，最小高度为\lfloor \log_2(n) \rfloor，最大高度为n-1。
3. 满二叉树的节点数与高度关系：一个高度为h 的满二叉树有2^{h+1} - 1 个节点。
递归
人脑不适合递归，而电脑却善于处理这种事情。如何用人脑的思维方式处理递归，这是需要练习的。要想使用递归，我们就需要一开始明白，什么时候需要递归来解决问题？
递归适合于解决下面这种问题：子问题和原问题是相似的，他们执行的代码也是相同的（类比循环），但是子问题需要把计算结果返回给上一级，这更适合用递归实现。
写递归有一套模板：
def recursive_function(params):
# 1. 确定边界（通常是输入参数的边界）
if edge_case_condition(params):
return edge_case_result
# 2. 处理基准情况（Base Case）
if base_case_condition(params):
return base_case_result
# 3. 处理递归情况（Recursive Case）
# 分解问题
smaller_problem_result1 = recursive_function(smaller_problem_params1)
smaller_problem_result2 = recursive_function(smaller_problem_params2)
# 处理更多子问题（如果有的话）
# 4. 组合结果并返回
result = combine_results(smaller_problem_result1, smaller_problem_result2)
return result推荐视频：
下面来看几道练习题：
《路径总和》
解答：
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
def dfs(node, nowSum):
# 边界条件
if node is None:
return False
# 基准条件
if node.left is None and node.right is None and nowSum == targetSum:
return True
# 分解子问题
flag = False
if node.left is not None: flag |= dfs(node.left, nowSum + node.left.val)
if node.right is not None: flag |= dfs(node.right, nowSum + node.right.val)
# 返回
return flag
return dfs(root, root.val) if root is not None else False注意注释把递归的函数分为了四部分，正对应上面的模板。
边界条件：当节点为空，说明碰到了边界，返回
False。基准条件：当该节点为叶子节点，并且路径总和等于目标总和，返回
True。分解子问题：递归寻找左节点和右节点，如果出现任何节点返回
True，向上返回True。返回结果：返回子问题获取的结果。
《统计二叉树中好节点的数目》
class Solution:
def goodNodes(self, root: TreeNode) -> int:
def dfs(root, maxNum) -> int:
# 边界条件
if root is None:
return 0
# 基准条件
ans = 0
ans += 1 if root.val >= maxNum else 0
# 子问题
ans += dfs(root.left, max(maxNum, root.val))
ans += dfs(root.right, max(maxNum, root.val))
# 返回
return ans
return dfs(root, -float('inf'))边界条件：节点为空，返回0；
基准条件：当这条路径上的最大值不大于节点值，给结果加1，否则不做处理。
子问题：递归寻找左子树和右子树的值，将其加到答案上，注意传入的是路径上的最大值。
返回：返回所有的加和。
二叉树算法
判断相同
如何判断两个树相同，分解成子问题就是：根节点相同，左子树相同，右子树相同，三个条件全部满足才相同。可以用递归解决，题目在这里：
解法（不是最简），易于理解：
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
def dfs(node1, node2):
# 边界条件
if node1 is None and node2 is None:
return True
if node1 is None or node2 is None:
return False
# 基准条件
flag = node1.val == node2.val
# 子问题
flag &= dfs(node1.left, node2.left)
flag &= dfs(node1.right, node2.right)
# 返回
return flag
return dfs(p, q)简洁写法，思路是一样的：
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if p is None or q is None:
return p is q
return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)判断对称
这是一棵对称的树，如何判断？
判断对称和判断相等相似：根节点相同，左节点等于另一个节点的右节点，右节点等于另一个节点的左节点。
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
def dfs(p, q):
if p is None or q is None:
return p is q
return p.val == q.val and dfs(p.left, q.right) and dfs(p.right, q.left)
# root的两个孩子相当于上一题的p和q
return dfs(root.left, root.right)判断平衡
如何判断一个二叉树是否是平衡二叉树？
分解成子问题就是：左子树的高度和右子树的高度相差不超过1。
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
flag = True
def dfs(node):
nonlocal flag
# 边界条件
if node is None:
return 0
# 基准条件&子问题
left_height = dfs(node.left)
right_height = dfs(node.right)
if abs(left_height - right_height) > 1:
flag = False
# 返回
return max(left_height, right_height) + 1
dfs(root)
return flag上面的递归函数计算的是该节点的层高，我们在递归函数中判断如果出现了不平衡的状态，就讲外置的变量置否。
判断二叉搜索树
递归的子问题就是：左子树的最大值小于根节点的值，右子树的最小值大于根节点的值：
解法：
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
flag = True
def dfs(node) -> [int, int]:
nonlocal flag
# 边界条件
if node is None:
return [float('inf'), -float('inf')]
# 子问题
left_min, left_max = dfs(node.left)
right_min, right_max = dfs(node.right)
if left_max >= node.val or right_min <= node.val:
flag = False
# 返回
return [min(node.val, left_min, right_min), max(node.val, left_max, right_max)]
dfs(root)
return flag以上是最一般的解法，之前我们提到过中序遍历二叉搜索树，其遍历结果是顺序的，可以用这个来进行判断。
尝试自己写一个中序遍历的判断吧。
评论区