LeetCode-树结构及其算法技巧总结

VocabVictor2024-09-022024-09-04

引言

树是一种非常重要的数据结构，在计算机科学中有广泛的应用。本文将介绍树的基本概念、常见类型，以及解决树相关问题的常用技巧。

1. 树的基本概念

树是由节点和边组成的数据结构，它具有以下特点：

有一个根节点
每个节点可以有零个或多个子节点
没有环路

最基本的树节点结构如下：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

2. 常见的树类型

2.1 二叉树

每个节点最多有两个子节点的树。

2.2 二叉搜索树（BST）

一种特殊的二叉树，其中每个节点的左子树中的值都小于该节点的值，右子树中的值都大于该节点的值。

2.3 平衡二叉树

一种维持平衡的二叉搜索树，如 AVL 树和红黑树。

2.4 完全二叉树

除了最后一层外，其他层都被完全填充，且最后一层的所有节点都尽可能地靠左。

2.5 满二叉树

除了叶节点外，每个节点都有两个子节点的二叉树。

3. 树的遍历方法

3.1 深度优先搜索（DFS）

前序遍历

def preorder(root):
    if not root:
        return
    print(root.val)
    preorder(root.left)
    preorder(root.right)

中序遍历

def inorder(root):
    if not root:
        return
    inorder(root.left)
    print(root.val)
    inorder(root.right)

后序遍历

def postorder(root):
    if not root:
        return
    postorder(root.left)
    postorder(root.right)
    print(root.val)

3.2 广度优先搜索（BFS）

from collections import deque

def levelOrder(root):
    if not root:
        return []
    queue = deque([root])
    result = []
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

4. 常见树问题解题技巧

4.1 递归

递归是解决树问题最常用的方法之一。

例如，计算树的最大深度：

def maxDepth(root):
    if not root:
        return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

4.2 迭代

有时，我们需要用迭代方法来解决树的问题，特别是在处理大规模数据时。

例如，使用栈进行前序遍历：

def preorderIterative(root):
    if not root:
        return []
    stack = [root]
    result = []
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return result

4.3 分治法

分治法常用于解决需要处理左右子树的问题。

例如，判断两棵树是否相同：

def isSameTree(p, q):
    if not p and not q:
        return True
    if not p or not q:
        return False
    return (p.val == q.val) and isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

4.4 层次遍历

层次遍历常用于需要逐层处理树节点的问题。

例如，找出二叉树的右视图：

def rightSideView(root):
    if not root:
        return []
    queue = deque([root])
    result = []
    while queue:
        level_size = len(queue)
        for i in range(level_size):
            node = queue.popleft()
            if i == level_size - 1:
                result.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return result