Czi.算法学习(三)

二叉树Part01

二叉树的递归遍历

注1：
在Python中，TreeNode 和链表节点（通常称作 ListNode）的定义在结构上非常相似，因为它们都是基于节点的数据结构。但是，它们在用途和一些关键属性上有所不同：

1. 结构目的

• 二叉树节点 (TreeNode)：用于构建二叉树，每个节点最多有两个子节点（左子节点和右子节点）。二叉树用于各种数据结构算法，如搜索、排序和作为决策树等。
• 链表节点 (ListNode)：用于构建链表，每个节点通常只有一个指向下一个节点的引用。链表是一种序列数据结构，用于实现队列、栈等或作为基础的数据存储结构。

2. 定义

尽管两者在类定义上看起来相似，通常如下所示：

• 二叉树节点：

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

• 链表节点：

  class ListNode:
      def __init__(self, val=0, next=None):
          self.val = val
          self.next = next
  

3. 关键属性区别

• TreeNode 有两个指针（left 和 right），这允许节点在树结构中向左或向右分支。
• ListNode 通常只有一个指针（next），这表示单向链表中的下一个节点。如果是双向链表，可能会有一个额外的 prev 指针指向前一个节点。

4. 用途区别

• 二叉树：广泛用于实现复杂的数据结构，如二叉搜索树、堆、红黑树等。它们支持快速搜索、添加和删除操作。
• 链表：用于实现可以动态增长和收缩的线性数据结构，适合用于实现没有固定大小限制的数据集合。它们允许快速的插入和删除操作，但访问速度较慢，因为需要从头节点开始逐一遍历。

5. 操作复杂性

• 在二叉树中进行插入、删除和查找通常涉及到比链表更复杂的逻辑，因为它们可能需要考虑到节点的左右平衡（特别是在平衡二叉树中）。
• 链表的操作通常比较直接，尤其是在单向链表中，插入和删除操作只需修改相邻节点的引用。

总结

尽管TreeNode和ListNode在结构上看起来相似，它们服务于不同的数据结构目的和应用场景。理解这些基础的数据结构对于学习更高级的算法和数据处理非常重要。

注2: extend和append递归访问左右子树的区别

在实现二叉树的前序遍历时，你确实可以使用 append() 方法来向结果列表添加元素，但这通常涉及到每次只添加一个元素。如果你想通过递归方法实现前序遍历并使用 append()，你需要稍微调整逻辑以适应逐个添加元素的方式。

下面是使用 append() 方法的递归前序遍历的实现示例：

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

class Solution:
    def preorderTraversal(self, root: TreeNode | None) -> list[int]:
        """
        使用递归方法实现二叉树的前序遍历，利用 append 方法添加元素。

        :param root: 二叉树的根节点。
        :return: 前序遍历的节点值列表。
        """
        result = []
        self._preorderHelper(root, result)
        return result

    def _preorderHelper(self, node: TreeNode | None, result: list[int]):
        """ 辅助函数用于递归遍历树，并使用 result 参数收集节点值。 """
        if node is None:
            return
        # 添加当前节点值
        result.append(node.val)
        # 递归遍历左子树
        self._preorderHelper(node.left, result)
        # 递归遍历右子树
        self._preorderHelper(node.right, result)

在这个实现中，preorderTraversal 函数初始化一个空列表 result，然后调用一个辅助函数 _preorderHelper 来递归地遍历树。这个辅助函数接收当前节点和结果列表作为参数。每访问一个节点，它就把节点的值添加到结果列表中，然后递归地处理左子树和右子树。

这种方法的好处是你可以避免在每个递归调用中创建新的列表，这可以稍微提高效率，因为使用 extend() 在某些情况下会涉及到额外的列表合并操作，而 append() 直接在现有列表上操作。此外，这种方式也使得辅助函数能够更自然地处理树的遍历过程，因为它不需要返回任何东西，只是修改了外部传入的列表。

144. 二叉树的前序遍历

leetcode链接

# Definition for a binary tree node.

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

class Solution:
    def preorderTraversal(self, root: TreeNode | None) -> list[int]:
        """
        实现二叉树的前序遍历。

        :param root: 二叉树的根节点。
        :return: 前序遍历的节点值列表。
        """
        if root is None:
            return []  # 返回空列表而不是 None

        result = []
        result.append(root.val)  # 访问根节点
        result.extend(self.preorderTraversal(root.left))  # 递归访问左子树
        result.extend(self.preorderTraversal(root.right))  # 递归访问右子树

        return result

if __name__ == '__main__':
    # 创建节点
    root = TreeNode(1)
    node2 = TreeNode(2)
    node3 = TreeNode(3)

    # 构建连接
    root.right = node2  # root的右子节点是2
    node2.left = node3  # node2的左子节点是3

    # 运行前序遍历并打印结果
    print(Solution().preorderTraversal(root))  # 应输出 [1, 2, 3]

145. 二叉树的后序遍历

leetcode链接

        result.extend(self.postorderTraversal(root.left))
        result.extend(self.postorderTraversal(root.right))
        result.append(root.val)

94. 二叉树的中序遍历

leetcode链接

        result.extend(self.inorderTraversal(root.left))
        result.append(root.val)
        result.extend(self.inorderTraversal(root.right))