数组·链表·哈希·二叉树高频算法面试题整理（Kotlin 题解，含最优解与其他解法）

算法题是 Android/后端面试绕不开的一关，而数组、链表、哈希表、二叉树是其中出现频率最高的四类数据结构。本文把力扣（LeetCode）与牛客网上高频出现的题目按这四类整理成一份复习清单，覆盖简单与中等难度。

每道题都遵循同一套结构：先讲清题意与思路，给出 Kotlin 实现，再对比暴力解等非最优解法，并分析时间/空间复杂度——面试真正的加分项往往不是”写出能跑的代码”，而是”能说清为什么这个解法最优、还有哪些解法各自差在哪里”。

本文所有代码基于 Kotlin，链表节点统一用 ListNode、二叉树节点统一用 TreeNode，定义如下，后续题目不再重复：

class ListNode(var value: Int) {
    var next: ListNode? = null
}

class TreeNode(var value: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

一、数组

数组考点集中在双指针、二分查找、滑动窗口、前缀和这几类技巧上，核心思想都是”用一次或有限次遍历替代嵌套遍历”。

1. 移动零（简单）

给定数组 nums，将所有 0 移到末尾，同时保持非零元素的相对顺序。要求原地操作。

最优解：双指针（快慢指针）。慢指针 slow 指向下一个非零元素应放的位置，快指针 fast 遍历数组，遇到非零就和 slow 交换并前移 slow。

/**
 * 移动零：将所有 0 移到数组末尾，保持非零元素相对顺序。
 * Move all zeros to the end while keeping the order of non-zero elements.
 * @param nums 待处理的整型数组
 */
fun moveZeroes(nums: IntArray) {
    var slow = 0
    for (fast in nums.indices) {
        if (nums[fast] != 0) {
            // 把非零元素交换到前面，slow 之前全是已排好的非零元素
            val tmp = nums[slow]
            nums[slow] = nums[fast]
            nums[fast] = tmp
            slow++
        }
    }
}

• 时间复杂度 O(n)，空间复杂度 O(1)，一次遍历原地完成。

非最优解：额外数组。开一个新数组，先拷贝所有非零元素，再补 0，最后写回。时间同样 O(n)，但空间退化到 O(n)，且不满足”原地”要求，面试中会被追问优化。

2. 最大子数组和（简单/中等）

找出 nums 中具有最大和的连续子数组，返回其和。例如 [-2,1,-3,4,-1,2,1,-5,4] 的答案是 6（子数组 [4,-1,2,1]）。

最优解：动态规划 / Kadane 算法。定义 cur 为”以当前元素结尾的最大子数组和”。若前面累积的和为负，不如从当前元素重新开始。

/**
 * 最大子数组和（Kadane 算法）。
 * Maximum subarray sum using Kadane's algorithm.
 * @param nums 整型数组
 * @return Int 最大连续子数组的和
 */
fun maxSubArray(nums: IntArray): Int {
    var cur = nums[0]   // 以当前元素结尾的最大和
    var best = nums[0]  // 全局最大和
    for (i in 1 until nums.size) {
        // 要么接在前面后面，要么从当前元素重新开始
        cur = maxOf(nums[i], cur + nums[i])
        best = maxOf(best, cur)
    }
    return best
}

• 时间 O(n)，空间 O(1)。

非最优解一：暴力枚举。双层循环枚举所有子数组起止点求和，O(n²)（甚至朴素求和到 O(n³)）。数据量一大就超时。

非最优解二：分治。把数组从中间劈开，最大子数组要么在左半、要么在右半、要么横跨中点，递归求解，O(n log n)。比暴力好但仍不如 Kadane，面试中作为”能想到多种解法”的加分项提一下即可。

3. 盛最多水的容器（中等）

数组 height 中每个元素代表一根竖线的高度，找出两条线与 x 轴围成容器可盛最多的水。

最优解：双指针。左右指针分别从两端向中间收缩。容器容量由较短的那条边决定，所以每次移动较短的一边——因为移动长边不可能让面积变大（宽度减小、高度上限还是被短边卡住）。

/**
 * 盛最多水的容器：双指针求最大面积。
 * Container with most water, solved with two pointers.
 * @param height 每根竖线的高度数组
 * @return Int 可容纳的最大水量
 */
fun maxArea(height: IntArray): Int {
    var left = 0
    var right = height.size - 1
    var best = 0
    while (left < right) {
        val area = minOf(height[left], height[right]) * (right - left)
        best = maxOf(best, area)
        // 移动较短的一边，才有可能获得更大面积
        if (height[left] < height[right]) left++ else right--
    }
    return best
}

• 时间 O(n)，空间 O(1)。

非最优解：暴力枚举。双层循环枚举每一对线求面积，O(n²)。双指针本质是”每次排除掉不可能更优的一大批组合”，把 O(n²) 降到 O(n)。

4. 三数之和（中等）

找出 nums 中所有和为 0 且不重复的三元组。

最优解：排序 + 双指针。先排序，固定一个数 nums[i]，在其右侧用左右双指针找两数之和为 -nums[i]。排序后可通过”跳过相同元素”天然去重。

/**
 * 三数之和：找出所有和为 0 的不重复三元组。
 * Find all unique triplets that sum to zero.
 * @param nums 整型数组
 * @return List 所有满足条件的三元组
 */
fun threeSum(nums: IntArray): List<List<Int>> {
    nums.sort()
    val res = mutableListOf<List<Int>>()
    for (i in nums.indices) {
        if (nums[i] > 0) break            // 最小值已 >0，后面不可能凑成 0
        if (i > 0 && nums[i] == nums[i - 1]) continue  // 跳过重复的固定值
        var left = i + 1
        var right = nums.size - 1
        while (left < right) {
            val sum = nums[i] + nums[left] + nums[right]
            when {
                sum < 0 -> left++
                sum > 0 -> right--
                else -> {
                    res.add(listOf(nums[i], nums[left], nums[right]))
                    // 跳过重复的左右值，避免重复三元组
                    while (left < right && nums[left] == nums[left + 1]) left++
                    while (left < right && nums[right] == nums[right - 1]) right--
                    left++
                    right--
                }
            }
        }
    }
    return res
}

• 时间 O(n²)（排序 O(n log n) + 外层遍历每次内层 O(n)），空间 O(log n)（排序栈开销，不计结果）。

非最优解：暴力三重循环 + 去重。O(n³) 枚举所有三元组，再用 Set 去重。逻辑直白但性能差，是”排序+双指针”要优化掉的对象。

5. 合并区间（中等）

给出若干区间 intervals，合并所有重叠区间。例如 [[1,3],[2,6],[8,10]] → [[1,6],[8,10]]。

最优解：按起点排序后线性合并。排序后，若当前区间起点 ≤ 结果中最后一个区间的终点，则重叠，合并（更新终点为两者较大值）；否则新开一个区间。

/**
 * 合并区间：合并所有重叠的区间。
 * Merge all overlapping intervals.
 * @param intervals 区间数组，每个元素为 [start, end]
 * @return Array 合并后的区间数组
 */
fun merge(intervals: Array<IntArray>): Array<IntArray> {
    if (intervals.isEmpty()) return emptyArray()
    // 按起点升序排序，保证重叠区间相邻
    intervals.sortBy { it[0] }
    val res = mutableListOf<IntArray>()
    for (interval in intervals) {
        val last = res.lastOrNull()
        if (last == null || interval[0] > last[1]) {
            res.add(interval)          // 不重叠，新开区间
        } else {
            last[1] = maxOf(last[1], interval[1])  // 重叠，扩展终点
        }
    }
    return res.toTypedArray()
}

• 时间 O(n log n)（瓶颈在排序），空间 O(log n)（不计结果数组）。

非最优解：两两比较反复合并。不排序，反复扫描数组两两判断是否重叠并合并，直到没有可合并的为止，最坏 O(n²) 甚至更差。排序把”任意两区间可能重叠”变成”只有相邻区间可能重叠”，是效率提升的关键。

6. 搜索旋转排序数组（中等）

升序数组在某点旋转（如 [0,1,2,4,5,6,7] 变成 [4,5,6,7,0,1,2]），在其中查找 target，存在返回下标否则返回 -1。要求 O(log n)。

最优解：改进二分。旋转数组的特点是：从中点劈开，必有一半是有序的。判断 target 是否落在有序的那一半区间内，据此决定往哪边收缩。

/**
 * 搜索旋转排序数组：在旋转后的升序数组中二分查找目标值。
 * Binary search in a rotated sorted array.
 * @param nums 旋转后的数组
 * @param target 目标值
 * @return Int 目标值下标，不存在返回 -1
 */
fun search(nums: IntArray, target: Int): Int {
    var left = 0
    var right = nums.size - 1
    while (left <= right) {
        val mid = left + (right - left) / 2
        when {
            nums[mid] == target -> return mid
            // 左半段有序
            nums[left] <= nums[mid] -> {
                if (target in nums[left]..nums[mid]) right = mid - 1
                else left = mid + 1
            }
            // 右半段有序
            else -> {
                if (target in nums[mid]..nums[right]) left = mid + 1
                else right = mid - 1
            }
        }
    }
    return -1
}

• 时间 O(log n)，空间 O(1)。

非最优解：线性扫描。直接遍历找 target，O(n)。能过但完全没用上”部分有序”这个条件，面试要求 O(log n) 时会被判不合格。

二、链表

链表考点几乎全部围绕指针操作：虚拟头节点（dummy）、快慢指针、迭代 vs 递归。链表题的通用技巧是用一个 dummy 头节点简化边界处理。

1. 反转链表（简单）

反转一个单链表。

最优解：迭代（三指针）。用 prev、cur 两个指针，边遍历边把 cur.next 指向 prev。

/**
 * 反转链表（迭代法）。
 * Reverse a singly linked list iteratively.
 * @param head 链表头节点
 * @return ListNode 反转后的新头节点
 */
fun reverseList(head: ListNode?): ListNode? {
    var prev: ListNode? = null
    var cur = head
    while (cur != null) {
        val next = cur.next  // 暂存下一个节点
        cur.next = prev      // 反转指针
        prev = cur           // prev、cur 同步后移
        cur = next
    }
    return prev
}

• 时间 O(n)，空间 O(1)。

非最优解：递归。递归到尾部再逐层反转指针，代码简洁但递归栈深度 O(n)，链表很长时有栈溢出风险：

/**
 * 反转链表（递归法）。
 * Reverse a singly linked list recursively.
 * @param head 链表头节点
 * @return ListNode 反转后的新头节点
 */
fun reverseListRecursive(head: ListNode?): ListNode? {
    if (head?.next == null) return head
    val newHead = reverseListRecursive(head.next)
    head.next!!.next = head  // 让下一个节点反过来指向自己
    head.next = null
    return newHead
}

• 时间 O(n)，空间 O(n)（递归栈）。因空间开销，迭代法更优。

2. 环形链表（简单）

判断链表中是否有环。

最优解：快慢指针（Floyd 判圈）。慢指针每次走一步，快指针每次走两步，若有环两者必然相遇；快指针走到 null 说明无环。

/**
 * 判断链表是否有环（快慢指针）。
 * Detect whether a linked list has a cycle.
 * @param head 链表头节点
 * @return Boolean 有环返回 true
 */
fun hasCycle(head: ListNode?): Boolean {
    var slow = head
    var fast = head
    while (fast?.next != null) {
        slow = slow?.next        // 慢指针走一步
        fast = fast.next?.next   // 快指针走两步
        if (slow === fast) return true  // 相遇即有环
    }
    return false
}

• 时间 O(n)，空间 O(1)。

非最优解：哈希表。遍历时把访问过的节点存入 Set，若再次遇到已存在的节点说明有环。时间 O(n) 但空间 O(n)。快慢指针把空间降到常数，是这道题的标准最优解。

3. 环形链表 II：返回入环节点（中等）

若链表有环，返回入环的第一个节点，否则返回 null。

最优解：快慢指针 + 数学推导。快慢指针相遇后，让一个指针从头出发、另一个从相遇点出发，同速前进，再次相遇处即入环点。设头到入环点距离 a、入环点到相遇点距离 b、相遇点回到入环点距离 c，由 2(a+b)=a+b+n(b+c) 可推出 a = c + (n-1)(b+c)，即从头走 a 步等于从相遇点绕若干圈后到入环点。

/**
 * 返回链表入环的第一个节点。
 * Return the node where the cycle begins, or null if no cycle.
 * @param head 链表头节点
 * @return ListNode 入环节点，无环返回 null
 */
fun detectCycle(head: ListNode?): ListNode? {
    var slow = head
    var fast = head
    while (fast?.next != null) {
        slow = slow?.next
        fast = fast.next?.next
        if (slow === fast) {
            // 相遇后，一个指针回到头，两指针同速前进再次相遇即入环点
            var ptr = head
            while (ptr !== slow) {
                ptr = ptr?.next
                slow = slow?.next
            }
            return ptr
        }
    }
    return null
}

• 时间 O(n)，空间 O(1)。

非最优解：哈希表。遍历节点存入 Set，第一个重复出现的节点就是入环点，O(n) 空间。逻辑更直观，但空间不如快慢指针。

4. 合并两个有序链表（简单）

将两个升序链表合并为一个新的升序链表。

最优解：迭代 + dummy 头节点。用一个虚拟头节点简化操作，每次取两链表头部较小的节点接到结果尾部。

/**
 * 合并两个有序链表。
 * Merge two sorted linked lists into one sorted list.
 * @param l1 第一个升序链表
 * @param l2 第二个升序链表
 * @return ListNode 合并后的升序链表头节点
 */
fun mergeTwoLists(l1: ListNode?, l2: ListNode?): ListNode? {
    val dummy = ListNode(0)  // 虚拟头节点，避免单独处理头部
    var tail = dummy
    var p1 = l1
    var p2 = l2
    while (p1 != null && p2 != null) {
        if (p1.value <= p2.value) {
            tail.next = p1
            p1 = p1.next
        } else {
            tail.next = p2
            p2 = p2.next
        }
        tail = tail.next!!
    }
    tail.next = p1 ?: p2  // 接上剩余部分
    return dummy.next
}

• 时间 O(m+n)，空间 O(1)。

非最优解：递归。每次比较头节点，递归合并剩余部分。代码更短但递归栈 O(m+n)，长链表有栈溢出风险，所以空间上不如迭代。

5. 删除链表的倒数第 N 个节点（中等）

删除链表倒数第 n 个节点并返回头节点，尽量一趟遍历完成。

最优解：快慢指针一次遍历。快指针先走 n 步，然后快慢指针同步前进，快指针到末尾时慢指针恰好停在待删节点的前一个。dummy 头节点用来优雅处理”删除的是头节点”这一边界。

/**
 * 删除链表的倒数第 N 个节点（一次遍历）。
 * Remove the n-th node from the end of the list in one pass.
 * @param head 链表头节点
 * @param n 倒数第几个（从 1 开始）
 * @return ListNode 删除后的链表头节点
 */
fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {
    val dummy = ListNode(0)
    dummy.next = head
    var fast: ListNode? = dummy
    var slow: ListNode? = dummy
    repeat(n) { fast = fast?.next }  // 快指针先走 n 步
    // 同步前进，直到快指针到末尾
    while (fast?.next != null) {
        fast = fast?.next
        slow = slow?.next
    }
    slow?.next = slow?.next?.next    // 跳过待删节点
    return dummy.next
}

• 时间 O(n)，空间 O(1)，只遍历一趟。

非最优解：两次遍历。第一趟统计链表长度 L，第二趟走到第 L-n 个节点删除。时间同为 O(n) 但需要遍历两趟。快慢指针的价值在于”一趟搞定”，面试题干里那句”尽量一趟完成”就是在暗示这个解法。

6. 相交链表（简单）

找到两个单链表相交的起始节点，不相交返回 null。

最优解：双指针走对方的路。两个指针分别从两条链表头出发，走到末尾后跳到对方链表头继续走。若相交，两指针会在交点相遇（都走了 a+b+c 的距离）；若不相交，会同时到达 null。

/**
 * 找到两个链表的相交起始节点。
 * Find the node at which two linked lists intersect.
 * @param headA 链表 A 的头节点
 * @param headB 链表 B 的头节点
 * @return ListNode 相交节点，不相交返回 null
 */
fun getIntersectionNode(headA: ListNode?, headB: ListNode?): ListNode? {
    var pA = headA
    var pB = headB
    // 走到头就换到对方链表，抵消长度差
    while (pA !== pB) {
        pA = if (pA == null) headB else pA.next
        pB = if (pB == null) headA else pB.next
    }
    return pA
}

• 时间 O(m+n)，空间 O(1)。

非最优解：哈希表。先把链表 A 的所有节点存入 Set，再遍历 B，第一个在 Set 中出现的节点即交点。O(m+n) 时间但 O(m) 空间。双指针巧妙地用”走对方的路”抵消了长度差，把空间降为常数。

三、哈希

哈希表的核心价值是用 O(1) 的查找替代 O(n) 的遍历，从而把很多”暴力双重循环 O(n²)“的问题优化到 O(n)。前缀和 + 哈希更是子数组类问题的杀手锏。

1. 两数之和（简单）

数组中找出和为 target 的两个数的下标。

最优解：哈希表一次遍历。边遍历边把 值→下标 存入哈希表，对每个数检查 target - 当前值 是否已在表中。

/**
 * 两数之和：返回和为 target 的两个数的下标。
 * Return indices of the two numbers that add up to target.
 * @param nums 整型数组
 * @param target 目标和
 * @return IntArray 两个数的下标
 */
fun twoSum(nums: IntArray, target: Int): IntArray {
    val map = HashMap<Int, Int>()  // 值 -> 下标
    for (i in nums.indices) {
        val need = target - nums[i]
        if (map.containsKey(need)) return intArrayOf(map[need]!!, i)
        map[nums[i]] = i
    }
    return intArrayOf()
}

• 时间 O(n)，空间 O(n)。

非最优解：暴力双重循环。枚举所有两数组合，O(n²) 时间、O(1) 空间。哈希表用 O(n) 的额外空间换来时间从 O(n²) 降到 O(n)，是典型的空间换时间。

2. 有效的字母异位词（简单）

判断字符串 t 是否是 s 的字母异位词（字母种类和个数完全相同，仅顺序不同）。

最优解：计数数组。仅含小写字母时，用长度 26 的数组统计：遍历 s 时对应字母 +1，遍历 t 时 -1，最后数组全为 0 则是异位词。

/**
 * 判断 t 是否为 s 的字母异位词。
 * Check whether t is an anagram of s.
 * @param s 源字符串
 * @param t 待判断字符串
 * @return Boolean 是异位词返回 true
 */
fun isAnagram(s: String, t: String): Boolean {
    if (s.length != t.length) return false
    val count = IntArray(26)
    for (c in s) count[c - 'a']++
    for (c in t) {
        count[c - 'a']--
        if (count[c - 'a'] < 0) return false  // t 中某字母数量超过 s
    }
    return true
}

• 时间 O(n)，空间 O(1)（固定 26 个字母）。

非最优解：排序比较。把两个字符串排序后比较是否相等。O(n log n) 时间，慢于计数法；但胜在能自然扩展到 Unicode 等更大字符集，可作为通用解法提及。

3. 字母异位词分组（中等）

将字符串数组中互为字母异位词的字符串分到同一组。

最优解：排序后的字符串作为哈希键。互为异位词的字符串排序后一定相同，用它作为 key 归类。

/**
 * 字母异位词分组。
 * Group anagrams together.
 * @param strs 字符串数组
 * @return List 分组后的结果
 */
fun groupAnagrams(strs: Array<String>): List<List<String>> {
    val map = HashMap<String, MutableList<String>>()
    for (str in strs) {
        // 排序后的字符串作为分组 key，异位词的 key 相同
        val key = str.toCharArray().sorted().joinToString("")
        map.getOrPut(key) { mutableListOf() }.add(str)
    }
    return map.values.toList()
}

• 时间 O(n·k log k)（n 个字符串，每个长 k 需排序），空间 O(n·k)。

非最优解：计数数组作为键。用每个字符串的 26 位字母计数（如 "a2b1c1"）作为 key，避免排序，把单个 key 的构造降到 O(k)，整体 O(n·k)。当字符串很长时比排序法更快，是一个可以主动抛出的进阶优化。

4. 最长连续序列（中等）

找出未排序数组中最长连续元素序列的长度，要求 O(n)。例如 [100,4,200,1,3,2] 的答案是 4（1,2,3,4）。

最优解：哈希表 + 只从序列起点扩展。把所有数存入 HashSet，只有当 num-1 不在集合中时（说明 num 是某段连续序列的起点）才向后逐一扩展计数，保证每个数最多被访问两次。

/**
 * 最长连续序列的长度。
 * Length of the longest consecutive elements sequence.
 * @param nums 未排序的整型数组
 * @return Int 最长连续序列长度
 */
fun longestConsecutive(nums: IntArray): Int {
    val set = nums.toHashSet()
    var best = 0
    for (num in set) {
        // 只从序列起点开始扩展，避免重复计算
        if (!set.contains(num - 1)) {
            var cur = num
            var len = 1
            while (set.contains(cur + 1)) {
                cur++
                len++
            }
            best = maxOf(best, len)
        }
    }
    return best
}

• 时间 O(n)（关键在”只从起点扩展”，否则会退化），空间 O(n)。

非最优解：排序。排序后遍历统计最长连续段，O(n log n)。逻辑简单但达不到题目要求的 O(n)。”只从起点扩展”这个剪枝是本题最容易被问到的细节。

5. 和为 K 的子数组（中等）

统计数组中和恰好为 k 的连续子数组的个数（元素可能为负，不能用滑动窗口）。

最优解：前缀和 + 哈希表。设前缀和 preSum[i]，则子数组 [j+1, i] 的和为 preSum[i] - preSum[j]。要它等于 k，即 preSum[j] = preSum[i] - k。用哈希表记录每个前缀和出现的次数，边遍历边查询。

/**
 * 统计和为 k 的连续子数组个数。
 * Count subarrays whose sum equals k.
 * @param nums 整型数组（可能含负数）
 * @param k 目标和
 * @return Int 满足条件的子数组个数
 */
fun subarraySum(nums: IntArray, k: Int): Int {
    val map = HashMap<Int, Int>()
    map[0] = 1        // 前缀和为 0 出现 1 次（对应空前缀）
    var preSum = 0
    var count = 0
    for (num in nums) {
        preSum += num
        // 存在前缀和为 preSum - k，则中间那段子数组和为 k
        count += map.getOrDefault(preSum - k, 0)
        map[preSum] = map.getOrDefault(preSum, 0) + 1
    }
    return count
}

• 时间 O(n)，空间 O(n)。

非最优解：暴力枚举。双层循环枚举所有子数组求和，O(n²)。因为数组含负数，无法用滑动窗口（和不单调），前缀和+哈希是本题的标准最优解——map[0]=1 这个初始化极易漏写，也是面试常考的细节。

四、二叉树

二叉树是递归思想的最佳练兵场。绝大多数题都能套用”先想清楚：当前节点该做什么、需要向左右子树要什么信息”这个框架。层序遍历则对应 BFS + 队列。

1. 二叉树的最大深度（简单）

返回二叉树的最大深度（根到最远叶子节点的节点数）。

最优解：递归（DFS）。深度 = max(左子树深度, 右子树深度) + 1。

/**
 * 二叉树的最大深度（递归）。
 * Maximum depth of a binary tree (DFS).
 * @param root 根节点
 * @return Int 最大深度
 */
fun maxDepth(root: TreeNode?): Int {
    if (root == null) return 0
    return maxOf(maxDepth(root.left), maxDepth(root.right)) + 1
}

• 时间 O(n)，空间 O(h)（h 为树高，递归栈开销；最坏退化为链表时 O(n)）。

非最优解：层序遍历（BFS）。用队列一层层遍历，统计层数。时间同为 O(n)，但需要队列存储，空间 O(n)（最宽一层的节点数）。递归写法更简洁，当担心递归栈溢出（树极深）时才改用 BFS。

2. 翻转二叉树（简单）

翻转一棵二叉树（每个节点的左右子树互换）。

最优解：递归。交换当前节点的左右孩子，再递归处理子树。

/**
 * 翻转二叉树。
 * Invert a binary tree.
 * @param root 根节点
 * @return TreeNode 翻转后的根节点
 */
fun invertTree(root: TreeNode?): TreeNode? {
    if (root == null) return null
    val tmp = root.left
    root.left = invertTree(root.right)
    root.right = invertTree(tmp)
    return root
}

• 时间 O(n)，空间 O(h)。

非最优解：迭代（BFS/DFS + 队列/栈）。用队列层序遍历，对每个出队节点交换左右孩子。时间同样 O(n)，空间 O(n)。递归写法足够优雅，迭代主要用于规避深树栈溢出。

3. 对称二叉树（简单）

判断一棵二叉树是否轴对称。

最优解：递归判断两棵子树是否镜像。两棵子树镜像的条件是：根值相等，且 左.left 镜像 右.right、左.right 镜像 右.left。

/**
 * 判断二叉树是否轴对称。
 * Check whether a binary tree is symmetric.
 * @param root 根节点
 * @return Boolean 对称返回 true
 */
fun isSymmetric(root: TreeNode?): Boolean {
    if (root == null) return true
    return isMirror(root.left, root.right)
}

/**
 * 判断两棵子树是否互为镜像。
 * Check whether two subtrees are mirror images of each other.
 * @param a 左子树节点
 * @param b 右子树节点
 * @return Boolean 互为镜像返回 true
 */
private fun isMirror(a: TreeNode?, b: TreeNode?): Boolean {
    if (a == null && b == null) return true
    if (a == null || b == null || a.value != b.value) return false
    return isMirror(a.left, b.right) && isMirror(a.right, b.left)
}

• 时间 O(n)，空间 O(h)。

非最优解：迭代 + 队列。每次成对入队要比较的节点（左.left 与 右.right、左.right 与 右.left），出队时比较。时间 O(n)、空间 O(n)，逻辑等价但代码更繁琐。

4. 二叉树的层序遍历（中等）

按层从上到下、每层从左到右返回节点值，结果按层分组。

最优解：BFS + 队列，按层处理。关键技巧是在每轮循环开始时记录当前队列长度，即为这一层的节点数，据此把同一层的节点收集到一个子列表。

/**
 * 二叉树的层序遍历。
 * Level-order traversal of a binary tree.
 * @param root 根节点
 * @return List 按层分组的节点值
 */
fun levelOrder(root: TreeNode?): List<List<Int>> {
    val res = mutableListOf<List<Int>>()
    if (root == null) return res
    val queue = ArrayDeque<TreeNode>()
    queue.add(root)
    while (queue.isNotEmpty()) {
        val size = queue.size          // 当前层的节点数
        val level = mutableListOf<Int>()
        repeat(size) {
            val node = queue.removeFirst()
            level.add(node.value)
            node.left?.let { queue.add(it) }
            node.right?.let { queue.add(it) }
        }
        res.add(level)
    }
    return res
}

• 时间 O(n)，空间 O(n)（队列最多存一层节点）。

非最优解：DFS + 记录深度。递归时携带当前深度 depth，把节点值放进 res[depth] 对应的子列表。时间 O(n)、空间 O(h)。能得到相同结果，但”层序”本质是 BFS，用 DFS 略显别扭，且不便处理”逐层”的变体（如锯齿遍历）。

5. 从前序与中序遍历序列构造二叉树（中等）

给定不含重复元素的前序遍历 preorder 和中序遍历 inorder，重建二叉树。

最优解：递归 + 哈希表定位根。前序的第一个元素是根，在中序中找到根的位置，其左边是左子树、右边是右子树。用哈希表把”中序值→下标”预存，避免每次线性查找。

/**
 * 从前序与中序遍历序列构造二叉树。
 * Build a binary tree from preorder and inorder traversal.
 * @param preorder 前序遍历序列
 * @param inorder 中序遍历序列
 * @return TreeNode 构造出的树的根节点
 */
fun buildTree(preorder: IntArray, inorder: IntArray): TreeNode? {
    // 中序值 -> 下标，O(1) 定位根在中序中的位置
    val idx = HashMap<Int, Int>()
    for (i in inorder.indices) idx[inorder[i]] = i

    fun build(preL: Int, preR: Int, inL: Int, inR: Int): TreeNode? {
        if (preL > preR) return null
        val rootVal = preorder[preL]      // 前序第一个是根
        val root = TreeNode(rootVal)
        val mid = idx[rootVal]!!          // 根在中序中的位置
        val leftSize = mid - inL          // 左子树节点数
        root.left = build(preL + 1, preL + leftSize, inL, mid - 1)
        root.right = build(preL + leftSize + 1, preR, mid + 1, inR)
        return root
    }
    return build(0, preorder.size - 1, 0, inorder.size - 1)
}

• 时间 O(n)，空间 O(n)（哈希表 + 递归栈）。

非最优解：每次线性扫描中序找根。不预存哈希表，每层递归都在中序数组里线性查找根的位置，最坏 O(n²)（树退化为链表时）。哈希表把定位从 O(n) 降到 O(1)，是本题的关键优化点。

6. 二叉树的最近公共祖先（中等）

找出二叉树中两个指定节点 p、q 的最近公共祖先（LCA）。

最优解：递归。对当前节点：若它等于 p 或 q，或它的左右子树各包含 p、q 之一，则它就是 LCA。递归返回值表示”该子树中找到了 p 或 q 中的谁”。

/**
 * 二叉树的最近公共祖先。
 * Lowest common ancestor of two nodes in a binary tree.
 * @param root 根节点
 * @param p 目标节点 p
 * @param q 目标节点 q
 * @return TreeNode 最近公共祖先节点
 */
fun lowestCommonAncestor(root: TreeNode?, p: TreeNode, q: TreeNode): TreeNode? {
    if (root == null || root === p || root === q) return root
    val left = lowestCommonAncestor(root.left, p, q)
    val right = lowestCommonAncestor(root.right, p, q)
    return when {
        left != null && right != null -> root  // 左右各找到一个，当前节点即 LCA
        else -> left ?: right                  // 否则返回非空的一侧
    }
}

• 时间 O(n)，空间 O(h)。

非最优解：记录父节点 + 路径回溯。先 DFS/BFS 记录每个节点的父指针，再从 p 一路向上把祖先存入 Set，然后从 q 向上找第一个在 Set 中的节点。时间 O(n)、空间 O(n)。递归解法一趟遍历即可，更简洁高效。

7. 验证二叉搜索树（中等）

判断一棵二叉树是否是合法的二叉搜索树（BST）：左子树所有值 < 根 < 右子树所有值。

最优解：中序遍历判断递增。BST 的中序遍历结果一定严格递增。遍历时维护前一个值 prev，若当前值 ≤ prev 则非法。

/**
 * 验证是否为合法的二叉搜索树（中序遍历法）。
 * Validate a binary search tree via inorder traversal.
 * @param root 根节点
 * @return Boolean 合法返回 true
 */
fun isValidBST(root: TreeNode?): Boolean {
    var prev: Long = Long.MIN_VALUE  // 用 Long 防止节点值为 Int.MIN_VALUE 的边界问题

    fun inorder(node: TreeNode?): Boolean {
        if (node == null) return true
        if (!inorder(node.left)) return false      // 遍历左子树
        if (node.value <= prev) return false        // 当前值必须严格大于前一个
        prev = node.value.toLong()
        return inorder(node.right)                  // 遍历右子树
    }
    return inorder(root)
}

• 时间 O(n)，空间 O(h)。

非最优解一：上下界递归。递归时给每个节点传入合法的取值区间 (min, max)，判断节点值是否在区间内并向下收缩边界。同样 O(n)，是一种等价的优秀解法，可作为备选答案。

非最优解二：只比较父子节点。仅判断 left.val < root.val < right.val 是错误解法——它只保证了相邻两层的关系，无法保证”左子树里最大值也小于根”。这是面试高频陷阱，务必主动指出为什么它是错的。

结语：解题的通用套路

回顾这四类题目，可以提炼出几条贯穿始终的优化思路：

数据结构	高频技巧	优化本质
数组	双指针、二分、前缀和	用一次/有限次遍历替代嵌套遍历，O(n²)→O(n) 或 O(log n)
链表	dummy 头节点、快慢指针	简化边界、一趟遍历替代多趟、常数空间替代哈希
哈希	哈希表、前缀和+哈希	空间换时间，O(1) 查找替代 O(n) 遍历
二叉树	递归（DFS）、BFS 队列	想清”当前节点做什么、向子树要什么信息”

💡 面试建议：面试时不要一上来就写最优解。先说暴力解、点明它的复杂度瓶颈，再自然引出优化思路，这个过程比直接背出最优解更能体现你的思维过程。写完代码后主动分析时空复杂度、说明边界处理（空输入、单节点、极端值），是拿高分的关键。