LeetCode Day 二叉树第 7 部分

在LeetCode的刷题过程中，二叉树相关题目是一个重要的模块。本部分文章将主要探讨二叉树的各种问题，通过剖析一些经典题目，帮助大家更加深入地理解二叉树的结构和算法。接下来，我们将分几个部分来讨论。

二叉树基础知识

在深入二叉树的题目之前，我们需要了解一些二叉树的基本概念。二叉树是一种树形数据结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树的基础操作包括插入、删除和查找，其应用广泛，尤其是在数据存储和检索方面。

二叉树的遍历方式

我们常见的二叉树遍历方式主要有三种：前序遍历、中序遍历和后序遍历。我们来看看这三种遍历的特点和实现方法。

class TreeNode {

    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
// 前序遍历
public void preOrder(TreeNode node) {
    if (node == null) return;
    System.out.print(node.val + " ");
    preOrder(node.left);
    preOrder(node.right);
}
// 中序遍历
public void inOrder(TreeNode node) {
    if (node == null) return;
    inOrder(node.left);
    System.out.print(node.val + " ");
    inOrder(node.right);
}
// 后序遍历
public void postOrder(TreeNode node) {
    if (node == null) return;
    postOrder(node.left);
    postOrder(node.right);
    System.out.print(node.val + " ");
}

经典二叉树题目分析

接下来，我们来分析几道经典的二叉树题目，这些题目能够帮助我们熟悉二叉树的不同操作和应用场景。

题目一：查找二叉搜索树的第k小元素

在一个二叉搜索树中，中序遍历的结果会是一个有序序列。因此，我们可以利用这种特性高效地找到第k小的元素。我们通过递归的方式进行中序遍历，直到计数达到k。代码实现如下：

int count = 0;

int result = 0;
public int kthSmallest(TreeNode root, int k) {
    inOrderTraversal(root, k);
    return result;
}
private void inOrderTraversal(TreeNode node, int k) {
    if (node == null) return;
    inOrderTraversal(node.left, k);
    count++;
    if (count == k) {
        result = node.val;
        return;
    }
    inOrderTraversal(node.right, k);
}

题目二：对称二叉树

对称二叉树是指一个树的左子树和右子树是镜像反转的。为了解决这个问题，我们可以借助递归来比较两个子树是否相等。实现代码如下：

public boolean isSymmetric(TreeNode root) {

    if (root == null) return true;
    return isMirror(root.left, root.right);
}
private boolean isMirror(TreeNode left, TreeNode right) {
    if (left == null && right == null) return true;
    if (left == null || right == null) return false;
    return (left.val == right.val)
        && isMirror(left.left, right.right)
        && isMirror(left.right, right.left);
}

总结与进阶

二叉树是一种非常重要的数据结构，熟练掌握二叉树的基本操作和常见算法对解决LeetCode上的问题是至关重要的。在进行更复杂的算法时，例如平衡树、红黑树等高级结构时，基本的二叉树知识都会成为你的基石。

希望本文能为你在LeetCode上的二叉树学习之路提供帮助。无论是基础操作还是进阶技巧，不断练习和实践才是掌握这些知识的最佳途径。祝你在编码的道路上越走越远！