❌

普通视图

发现新文章，点击刷新页面。
昨天以前首页

从输入URL到页面显示的完整技术流程

✇掘金 前端
作者 Wect
2026年2月22日 13:53

一、引言

在Web应用场景中，用户输入统一资源定位符（URL）到页面最终渲染显示，是一个涉及浏览器、网络协议、服务器交互的复杂技术链路。该链路涵盖URL解析、DNS域名解析、TCP/TLS连接建立、HTTP请求响应、浏览器渲染等多个核心环节，各环节紧密衔接、协同工作，直接决定了页面加载速度与交互体验。本文将从技术原理出发，系统拆解整个流程的核心机制，梳理各环节的关键技术要点，为相关技术研究、开发实践及面试备考提供严谨、客观的参考依据。

二、主体分析：从URL到页面显示的完整流程

（一）URL解析：资源定位的前置准备

URL作为Web资源的唯一标识，浏览器接收用户输入的字符串后，首先需完成URL的解析与补全，确保能够准确定位目标服务器及对应资源。该过程的核心是校验URL合法性，并拆解其核心组成部分。

浏览器会对输入字符串进行格式校验，判断其是否符合URL标准规范。若输入字符串不完整（如仅输入“www.example.com”），浏览器将自动补全协议、默认端口等必要字段，补全后为“www.example.com/”；其中，HTTPS协…

一个完整的URL结构可拆解为六个核心部分，以“www.example.com:443/path?query=…

  • 协议（scheme）：即https，用于定义浏览器与服务器之间的通信规则，常用协议还包括HTTP、FTP等；

  • 域名（host）：即www.example.com，作为服务器的别名，用于简化用户记忆，需通过DNS解析转换为网络可识别的IP地址；

  • 端口（port）：即443，用于区分服务器上的不同服务，默认端口可省略；

  • 路径（path）：即/path，用于指定服务器上具体资源的存储位置，如“/index.html”对应服务器根目录下的首页文件；

  • 查询参数（query）：即?query=1，用于向服务器传递额外请求参数，多个参数以“&”分隔；

  • 锚点（hash）：即#hash，用于定位页面内的具体位置，仅在浏览器本地生效，不会随HTTP请求发送至服务器。

（二）DNS查询：域名与IP的映射转换

网络通信的本质是IP地址之间的交互，服务器与客户端仅能通过IP地址识别彼此。由于IP地址具有复杂性、难记忆的特点，DNS（域名系统）应运而生，其核心功能是实现域名到IP地址的映射转换，相当于网络世界的“通讯录”。

DNS查询遵循“从近到远、从本地到远程”的顺序，优先查询本地缓存以提升查询效率，缓存未命中时再发起远程查询，完整流程如下：

  1. 浏览器DNS缓存：浏览器会缓存近期查询过的域名-IP映射关系，缓存有效期较短（通常为几分钟至几小时），查询时优先匹配，命中则直接获取IP地址；

  2. 操作系统DNS缓存：若浏览器缓存未命中，将查询操作系统自带的DNS缓存，如Windows系统的hosts缓存、Mac系统的DNS缓存；

  3. 本地hosts文件：操作系统缓存未命中时，读取本地hosts文件，该文件可手动配置域名与IP的映射关系，常用于开发测试场景（如配置“127.0.0.1 localhost”）；

  4. 本地DNS服务器：以上缓存均未命中时，向本地DNS服务器（通常由网络运营商提供，如电信、联通DNS服务器）发送查询请求，运营商服务器会缓存常用域名的解析结果；

  5. 递归与迭代查询：若本地DNS服务器未缓存目标域名解析结果，将通过“递归+迭代”的方式逐层查询，依次向根域名服务器、顶级域名服务器（如.com、.cn服务器）、目标域名服务器发起请求，最终获取目标IP地址，并返回给浏览器同时进行缓存。

DNS查询的核心机制可分为递归查询与迭代查询：客户端与本地DNS服务器之间采用递归查询，即客户端仅需等待最终解析结果，由本地DNS服务器完成全程查询操作；DNS服务器之间采用迭代查询，即各服务器仅告知后续查询的目标服务器地址，不负责全程查询，直至获取最终IP地址。

（三）TCP/TLS握手：可靠安全连接的建立

获取目标服务器IP地址后，浏览器需与服务器建立通信连接，其中HTTP协议基于TCP协议实现可靠数据传输，HTTPS协议则在TCP协议之上增加TLS协议，实现数据加密与身份校验，保障通信安全。

1. TCP三次握手：可靠连接的建立

TCP（传输控制协议）的核心特性是可靠传输，三次握手是建立TCP连接的必要流程，其目的是确认双方的发送能力与接收能力均正常，避免历史延迟请求引发的错误连接，保障连接可靠性。三次握手流程如下：

  1. 客户端向服务器发送SYN报文，发起连接请求，告知服务器客户端准备建立连接；

  2. 服务器接收SYN报文后，返回SYN+ACK报文，确认接收客户端请求，同时向客户端发起连接请求；

  3. 客户端接收SYN+ACK报文后，返回ACK报文，确认接收服务器请求，完成三次握手。

三次握手的合理性可通过对比分析验证：若仅采用两次握手，服务器发送SYN+ACK报文后即确认连接建立，但无法确认客户端是否能接收自身报文，若客户端ACK报文丢失，服务器将持续等待，造成资源浪费；若采用四次握手，将在三次握手基础上增加额外确认步骤，不会提升连接可靠性，反而会增加通信延迟，降低传输效率。

2. TLS握手：安全通信的保障

HTTPS协议是HTTP协议与TLS（传输层安全协议）的结合，相比HTTP协议的明文传输，HTTPS通过TLS握手实现身份校验与数据加密，避免数据被窃取、篡改。TLS握手的核心操作如下：

  1. 加密算法协商：客户端与服务器协商一致，确定双方均支持的加密算法（如AES对称加密、RSA非对称加密），确保后续数据加密与解密可正常执行；

  2. 服务器证书校验：服务器向客户端发送由权威CA机构颁发的SSL证书，客户端校验证书的合法性（包括证书有效期、是否被篡改等），确认服务器身份的真实性，避免中间人劫持；

  3. 对称密钥生成：证书校验通过后，客户端与服务器协商生成对称密钥，后续所有HTTP请求与响应数据均通过该密钥加密/解密，兼顾安全性与传输效率；

  4. 握手完成确认：双方确认TLS握手完成，后续通信数据将采用协商好的对称密钥进行加密传输，保障通信安全。

与HTTP协议相比，HTTPS协议的核心差异的是增加了TLS握手环节，通过身份校验与数据加密，解决了HTTP协议明文传输的安全隐患。

（四）HTTP请求与响应：资源的传输交互

TCP（或TLS+TCP）连接建立完成后，浏览器向服务器发起HTTP请求，服务器接收请求并处理后，返回HTTP响应，完成Web资源的传输交互，这是整个链路中资源传递的核心环节。

1. HTTP请求报文

HTTP请求报文由请求行、请求头、空行、请求体四部分组成，简化示例如下：

GET /index.html HTTP/1.1  # 请求行：请求方法 + 资源路径 + HTTP版本
Host: www.example.com     # 请求头：传递额外请求信息
Cookie: username=test
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) Chrome/120.0.0.0
                          # 空行：分隔请求头与请求体
# 请求体：GET请求通常为空，POST请求用于传递表单等参数

常用HTTP请求方法包括：GET（用于获取Web资源，如打开页面）、POST（用于提交数据，如登录、表单提交）、PUT（用于修改资源）、DELETE（用于删除资源），不同请求方法对应不同的服务器处理逻辑。

2. HTTP响应报文

HTTP响应报文与请求报文对应，由响应行、响应头、空行、响应体四部分组成，简化示例如下：

HTTP/1.1 200 OK          # 响应行：HTTP版本 + 状态码 + 状态描述
Content-Type: text/html  # 响应头：传递资源相关信息
Content-Length: 1024
Cache-Control: max-age=3600

<html><head><title>示例页面</title></head><body>...</body></html>  # 响应体：核心Web资源

3. 常见HTTP状态码

HTTP状态码用于告知浏览器请求处理结果，分为5大类，核心常用状态码如下：

  • 200 OK：请求处理成功，服务器正常返回目标资源，是最常见的状态码；

  • 301 永久重定向：请求的资源已永久迁移至新地址，浏览器将自动跳转至新地址；

  • 302 临时重定向：请求的资源临时迁移至新地址，跳转行为仅在本次请求有效；

  • 304 Not Modified：目标资源未发生修改，浏览器可直接使用本地缓存，提升加载速度；

  • 404 Not Found：请求的资源不存在，通常由URL输入错误、资源被删除导致；

  • 500 Internal Server Error：服务器内部出现错误（如代码报错、服务器宕机），与客户端请求无关。

（五）浏览器解析：渲染前置的结构构建

浏览器接收服务器返回的HTTP响应后，若响应体为HTML资源，不会直接渲染显示，需先完成HTML、CSS、JS的解析，构建DOM树、CSSOM树及渲染树（Render Tree），为后续页面渲染提供基础结构，这是页面渲染的前置环节。

1. HTML解析与DOM树构建

浏览器对HTML的解析遵循自上而下、逐行解析的原则，将HTML文档中的标签、文本、属性等，转换为浏览器可识别的文档对象模型树（DOM Tree）。DOM Tree的根节点为标签，各子节点对应HTML中的各类元素，层级结构与HTML文档保持一致。

该解析过程的核心特点是：遇到未添加defer/async属性的<script>标签时，会阻塞HTML解析。原因在于JavaScript代码可能对DOM进行操作（如修改、删除DOM节点），浏览器需先执行完JavaScript代码，再继续解析后续HTML内容，避免解析结果与JS操作冲突。

2. CSS解析与CSSOM树构建

CSS解析与HTML解析可并行执行，不依赖HTML解析顺序，但会阻塞页面渲染。浏览器将页面中所有CSS样式（内联样式、内部样式、外部样式）解析后，构建CSS对象模型树（CSSOM Tree），该树明确了每个DOM节点对应的样式规则（如字体、颜色、尺寸等）。

若JavaScript代码中存在获取元素样式的操作（如getComputedStyle()），浏览器将先完成CSS解析与CSSOM树构建，再执行对应的JavaScript代码，确保JS获取的样式信息准确无误。

3. 渲染树（Render Tree）构建

DOM树与CSSOM树构建完成后，浏览器将两者合并，生成渲染树（Render Tree）。渲染树的核心特点是仅包含页面可见节点，不可见节点（如display: none属性的元素）不会被纳入渲染树，避免无效渲染；而visibility: hidden属性的元素，虽视觉上隐藏但仍占据页面布局空间，会被纳入渲染树。渲染树是后续页面布局、绘制的核心依据。

（六）页面渲染：视觉呈现的核心流程

渲染树构建完成后，浏览器通过布局（Layout）、绘制（Paint）、合成（Composite）三个依次执行的核心步骤，将Web资源渲染显示在屏幕上，形成用户最终看到的页面，该流程直接决定页面的视觉呈现效果与加载效率。

1. 布局（Layout）：元素位置与尺寸的计算

布局又称回流或重排，其核心作用是根据渲染树，计算每个可见元素的位置与尺寸，包括元素的宽度、高度、left/top坐标等，明确每个元素在页面中的具体布局位置。

触发布局的常见场景包括：元素尺寸或位置修改（如修改width、height、margin属性）、页面窗口大小调整、DOM节点的添加或删除等，布局操作会触发后续绘制与合成步骤，对页面加载效率有一定影响。

2. 绘制（Paint）：元素视觉样式的绘制

绘制又称重绘，其核心作用是根据布局计算的结果，在浏览器的绘制层上，为每个元素绘制视觉样式，包括颜色、边框、背景、文字、图片等，将元素的视觉属性呈现出来。

触发绘制的常见场景包括：元素视觉样式修改（如修改color、background-color、border-color属性），但元素尺寸与位置未发生变化，此时仅触发绘制与合成步骤，无需重新执行布局，效率高于布局操作。

3. 合成（Composite）：分层渲染与屏幕显示

合成又称分层合成，其核心作用是将绘制完成的多个绘制层，通过GPU（图形处理器）进行分层合成，将所有绘制层整合为一个完整的页面，最终渲染显示在屏幕上。

GPU分层合成的优势在于效率高，不同绘制层相互独立，修改某一层的元素时，无需重新绘制整个页面，仅需重新合成该层即可，可显著提升页面交互的流畅度。例如，修改元素的transform属性（GPU加速属性）时，仅触发合成步骤，无需执行布局与绘制，效率最优。

（七）完整流程汇总

从输入URL到页面显示的完整技术流程可总结为：用户输入URL后，浏览器先完成URL解析与补全，明确通信协议、域名、端口等核心信息；通过DNS解析系统，将域名转换为对应的IP地址；与服务器建立TCP连接，HTTPS协议额外执行TLS握手确保通信安全；连接建立后，浏览器发送HTTP请求，服务器处理后返回HTTP响应；浏览器解析HTML构建DOM树、解析CSS构建CSSOM树，合并生成渲染树；最后通过布局、绘制、合成三个步骤，将页面渲染显示在屏幕上，完成整个流程。

（八）追问常见

1. DNS 是递归还是迭代？

DNS查询的核心机制分为递归查询与迭代查询，二者应用场景不同、职责明确：客户端与本地DNS服务器之间采用递归查询，即客户端无需参与中间查询过程，仅需等待本地DNS服务器返回最终的IP解析结果，全程由本地DNS服务器完成逐层查询操作；DNS服务器之间（包括本地DNS服务器与根域名服务器、顶级域名服务器、目标域名服务器之间）采用迭代查询，即各服务器仅向发起查询的服务器告知后续查询的目标服务器地址，不负责全程查询，直至某一服务器返回最终IP地址，查询流程终止。

2. HTTPS 比 HTTP 多了哪一步？

与HTTP协议相比，HTTPS协议的核心差异是增加了TLS（传输层安全协议）握手环节。HTTP协议基于TCP协议进行明文传输，数据易被窃取、篡改，无身份校验机制；而HTTPS协议在TCP三次握手建立连接后，会额外执行TLS握手流程，完成加密算法协商、服务器证书校验、对称密钥生成等操作，实现通信数据的加密传输与服务器身份的真实性校验，从而解决HTTP协议明文传输的安全隐患，保障网络通信的安全性。

3. TCP 三次握手为什么是三次？

TCP三次握手的核心目的是确认通信双方的发送能力与接收能力均正常，同时避免历史延迟请求引发的错误连接，保障TCP连接的可靠性，其次数设定具有明确的合理性，既不能减少为两次，也无需增加至四次。若仅采用两次握手，服务器发送SYN+ACK报文后即确认连接建立，但无法确认客户端是否能接收自身发送的报文，若客户端的ACK报文丢失，服务器会持续等待连接，造成服务器资源浪费；若采用四次握手，会在三次握手的基础上增加额外的确认步骤，该步骤无法提升连接的可靠性，反而会增加网络通信延迟，降低数据传输效率，因此三次握手是兼顾可靠性与效率的最优选择。

三、结论

从输入URL到页面显示的过程，是浏览器、网络协议与服务器协同工作的集中体现，涵盖URL解析、DNS查询、TCP/TLS连接、HTTP请求响应、浏览器解析与渲染六大核心环节，各环节环环相扣、缺一不可。其中，URL解析与DNS查询为资源定位提供基础，TCP/TLS连接保障通信的可靠与安全，HTTP请求响应实现资源传输，浏览器解析与渲染完成页面视觉呈现。

深入理解该技术流程，不仅能够帮助开发者优化页面加载速度、提升用户体验，解决开发中的各类网络与渲染相关问题，同时也是计算机网络、前端开发等领域面试的核心考点。

LeetCode 105. 从前序与中序遍历序列构造二叉树：题解与思路解析

✇掘金 前端
作者 Wect
2026年2月19日 19:53

在二叉树的算法题型中，“根据遍历序列构造二叉树”是经典考点，而 LeetCode 105 题——从前序与中序遍历序列构造二叉树，更是这一考点的核心代表。这道题不仅能考察我们对二叉树遍历规则的理解，还能检验递归思维和哈希表优化的应用，今天就来一步步拆解这道题，从思路到代码，吃透每一个细节。

一、题目回顾

题目给出两个整数数组preorder 和 inorder，其中 preorder 是二叉树的先序遍历序列，inorder 是同一棵二叉树的中序遍历序列，要求我们构造这棵二叉树并返回其根节点。

补充基础：二叉树遍历规则

  • 先序遍历（preorder）：根节点 → 左子树 → 右子树（根在前，左右在后）；

  • 中序遍历（inorder）：左子树 → 根节点 → 右子树（根在中间，左右分居两侧）。

核心关键：先序遍历的第一个元素一定是二叉树的根节点；而中序遍历中，根节点左侧的所有元素是左子树的中序序列，右侧的所有元素是右子树的中序序列。利用这两个特性，我们就能递归地构造出整个二叉树。

二、解题思路（核心逻辑）

这道题的解题核心是「递归分治」，配合哈希表优化查找效率，具体思路可以分为 4 步，我们结合例子来理解（假设 preorder = [3,9,20,15,7]，inorder = [9,3,15,20,7]）：

步骤1：确定根节点

根据先序遍历规则，preorder 的第一个元素 preorder[0] 就是整个二叉树的根节点（例子中根节点是 3）。

步骤2：划分左右子树的中序序列

在中序序列 inorder 中找到根节点的索引（例子中 3 的索引是 1）：

  • 根节点左侧的元素（[9]）：左子树的中序序列；

  • 根节点右侧的元素（[15,20,7]）：右子树的中序序列。

步骤3：划分左右子树的先序序列

左右子树的节点数量，在中序序列和先序序列中是一致的：

  • 左子树的节点数 = 根节点在中序的索引 - 中序序列的起始索引（例子中 1 - 0 = 1，左子树有 1 个节点）；

  • 因此，先序序列中，根节点之后的「左子树节点数」个元素（[9]）是左子树的先序序列；

  • 剩下的元素（[20,15,7]）是右子树的先序序列。

步骤4：递归构造左右子树

对左子树和右子树，重复上述 3 个步骤：找到子树的根节点、划分左右子序列，直到序列为空（递归终止条件），最终拼接出整个二叉树。

优化点：哈希表加速查找

如果每次在中序序列中查找根节点都用遍历的方式，时间复杂度会达到 O(n²)（n 是节点总数）。我们可以提前用哈希表（Map）存储中序序列中「元素 → 索引」的映射，这样每次查找根节点的索引只需 O(1) 时间，整体时间复杂度优化到 O(n)。

三、完整代码实现（TypeScript）

先给出 TreeNode 类的定义（题目已提供，此处复用并补充注释），再实现核心的 buildTree 函数，每一步代码都附上详细注释，方便理解：

// 二叉树节点类定义
class TreeNode {
  val: number
  left: TreeNode | null  // 左子节点，默认为null
  right: TreeNode | null // 右子节点，默认为null
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = (val === undefined ? 0 : val) // 节点值，默认0
    this.left = (left === undefined ? null : left)
    this.right = (right === undefined ? null : right)
  }
}

function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
  // 1. 构建中序序列的哈希映射，key是节点值，value是对应索引
  const map = new Map<number, number>();
  inorder.forEach((val, index) => {
    map.set(val, index);
  });

  /**
   * 递归辅助函数：构造当前范围内的二叉树
   * @param preorderStart 先序序列当前范围的起始索引
   * @param preorderEnd 先序序列当前范围的结束索引
   * @param inorderStart 中序序列当前范围的起始索引
   * @param inorderEnd 中序序列当前范围的结束索引
   * @returns 当前范围的二叉树根节点
   */
  const helper = (
    preorderStart: number, 
    preorderEnd: number, 
    inorderStart: number, 
    inorderEnd: number
  ): TreeNode | null => {

    // 递归终止条件：当前范围无节点（起始索引>结束索引），返回null
    if (preorderStart > preorderEnd || inorderStart > inorderEnd) {
      return null;
    }

    // 2. 确定当前范围的根节点（先序序列的第一个元素）
    const rootVal = preorder[preorderStart];
    const root = new TreeNode(rootVal); // 创建根节点

    // 3. 找到根节点在中序序列中的索引，用于划分左右子树
    const inorderIndex = map.get(rootVal)!; // ！表示非null断言（确保能找到索引）
    const leftSize = inorderIndex - inorderStart; // 左子树的节点数

    // 4. 递归构造左子树
    // 左子树先序范围：preorderStart+1 ~ preorderStart+leftSize（根节点后leftSize个元素）
    // 左子树中序范围：inorderStart ~ inorderIndex-1（根节点左侧元素）
    root.left = helper(
      preorderStart + 1, 
      preorderStart + leftSize, 
      inorderStart, 
      inorderIndex - 1
    );

    // 5. 递归构造右子树
    // 右子树先序范围：preorderStart+leftSize+1 ~ preorderEnd（左子树之后的剩余元素）
    // 右子树中序范围：inorderIndex+1 ~ inorderEnd（根节点右侧元素）
    root.right = helper(
      preorderStart + leftSize + 1, 
      preorderEnd, 
      inorderIndex + 1, 
      inorderEnd
    );

    return root; // 返回当前范围的根节点
  }

  // 初始调用递归函数，范围是整个先序和中序序列
  return helper(0, preorder.length - 1, 0, inorder.length - 1);
};

四、代码关键细节解析

1. 递归终止条件

当 preorderStart > preorderEnd 或 inorderStart > inorderEnd 时，说明当前范围内没有节点，返回 null（比如叶子节点的左右子节点，就会触发这个条件）。

2. 左子树节点数的计算

leftSize = inorderIndex - inorderStart，这个计算是划分先序序列的关键——因为先序序列中，根节点之后的 leftSize 个元素，必然是左子树的先序序列，剩下的就是右子树的先序序列。

3. 哈希表的非null断言

代码中 map.get(rootVal)! 用到了 TypeScript 的非null断言（!），原因是题目保证了 preorder 和 inorder 是同一棵二叉树的遍历序列，因此根节点的值一定能在中序序列中找到，不会返回 null。

4. 时间和空间复杂度

  • 时间复杂度：O(n)，n 是节点总数。哈希表构建需要 O(n) 时间，递归过程中每个节点被处理一次，每次查找根节点索引是 O(1)；

  • 空间复杂度：O(n)，哈希表存储 n 个元素，递归调用栈的深度最坏情况下是 O(n)（比如斜树），最好情况下是 O(log n)（平衡二叉树）。

五、常见易错点提醒

  1. 先序序列的划分错误：容易把右子树的先序起始索引算错，记住是 preorderStart + leftSize + 1（跳过根节点和左子树）；

  2. 中序序列的边界错误：左子树的中序结束索引是 inorderIndex - 1，右子树的中序起始索引是 inorderIndex + 1，容易漏写 ±1 导致死循环；

  3. 忽略空数组情况：当 preorder 和 inorder 为空时，直接返回 null（递归终止条件会处理，但需注意初始调用时的边界）；

  4. 不用哈希表优化：直接遍历中序序列找根节点，会导致时间复杂度飙升，在 n 较大时（比如 10^4 级别）会超时。

六、总结

LeetCode 105 题的核心是「利用遍历序列的特性 + 递归分治 + 哈希表优化」，解题的关键在于抓住“先序定根、中序分左右”的规律，再通过递归逐步构造子树。

这道题不仅能帮我们巩固二叉树的遍历知识，还能锻炼递归思维——递归的本质就是“把大问题拆成小问题，解决小问题后拼接结果”，这里的大问题是“构造整个二叉树”，小问题是“构造左子树”和“构造右子树”。

如果能吃透这道题，再遇到“从中序与后序遍历构造二叉树”（LeetCode 106 题）就会事半功倍，因为思路完全相通，只是根节点的位置和序列划分方式略有不同。

LeetCode 106. 从中序与后序遍历序列构造二叉树：题解+思路拆解

✇掘金 前端
作者 Wect
2026年2月19日 20:17

在二叉树的算法题中，“根据遍历序列构造二叉树”是高频考点，而 LeetCode 106 题（从中序与后序遍历序列构造二叉树）更是经典中的经典。它不仅考察对二叉树遍历规则的理解，还需要运用分治思想拆解问题，新手容易在“区间划分”上栽坑。今天就带大家一步步拆解这道题，从思路分析到代码实现，再到细节避坑，彻底搞懂如何通过两个遍历序列还原二叉树。

一、题目核心认知

先明确题目要求，避免理解偏差：

  • 给定两个整数数组 inorder（中序遍历）和 postorder（后序遍历），二者对应同一棵二叉树；

  • 构造并返回这棵二叉树的根节点；

  • 默认输入有效（无重复元素，且两个数组长度一致，能构成合法二叉树）。

关键前提：二叉树遍历规则回顾

要解决这道题，必须牢记中序和后序遍历的核心特点（这是解题的灵魂）：

  1. 中序遍历（左-根-右）：先遍历左子树，再访问根节点，最后遍历右子树；

  2. 后序遍历（左-右-根）：先遍历左子树，再遍历右子树，最后访问根节点。

核心突破口：后序遍历的最后一个元素，一定是当前二叉树的根节点；而中序遍历中，根节点左侧的所有元素都是左子树的节点，右侧的所有元素都是右子树的节点。

二、解题思路拆解（分治思想）

既然能通过后序找到根节点，通过中序划分左右子树，那我们就可以用「分治」的思路，把大问题拆成小问题，递归求解：

步骤1：找到根节点

取 postorder 的最后一个元素，作为当前二叉树的根节点（root）。

步骤2：划分中序遍历的左右子树区间

在inorder 中找到根节点的索引（记为 rootIndex），则：

  • 左子树的中序区间：[inorderStart, rootIndex - 1]（根节点左侧所有元素）；

  • 右子树的中序区间：[rootIndex + 1, inorderEnd]（根节点右侧所有元素）。

步骤3：划分后序遍历的左右子树区间

后序遍历的区间长度和中序遍历一致（因为对应同一棵子树），设左子树的节点个数为 leftSize = rootIndex - inorderStart，则：

  • 左子树的后序区间：[postorderStart, postorderStart + leftSize - 1]（左子树节点个数为 leftSize）；

  • 右子树的后序区间：[postorderStart + leftSize, postorderEnd - 1]（去掉最后一个根节点，剩余部分前半为左子树，后半为右子树）。

步骤4：递归构造左右子树

用同样的方法，递归构造左子树和右子树，分别赋值给根节点的 left 和 right 指针。

步骤5：优化索引查询（避免重复遍历）

如果每次在中序数组中找根节点索引都用遍历的方式，时间复杂度会很高（O(n²)）。我们可以提前用一个哈希表（Map），存储中序数组中「元素-索引」的映射，这样每次查询根节点索引只需 O(1) 时间，整体时间复杂度优化到 O(n)。

三、完整代码实现（TypeScript）

结合上面的思路，我们来实现代码（题目已给出 TreeNode 类，直接复用即可）：

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

class TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = (val === undefined ? 0 : val)
    this.left = (left === undefined ? null : left)
    this.right = (right === undefined ? null : right)
  }
}

function buildTree(inorder: number[], postorder: number[]): TreeNode | null {
  // 提前存储中序遍历的「元素-索引」映射，优化查询效率
  const map = new Map<number, number>();
  inorder.forEach((val, index) => {
    map.set(val, index);
  });

  // 递归辅助函数：根据区间构造子树
  // inorderStart/inorderEnd：当前子树在中序数组中的区间
  // postorderStart/postorderEnd：当前子树在后序数组中的区间
  const helper = (inorderStart: number, inorderEnd: number, postorderStart: number, postorderEnd: number): TreeNode | null => {
    // 递归终止条件：区间不合法（没有节点），返回null
    if (inorderStart > inorderEnd || postorderStart > postorderEnd) {
      return null;
    }

    // 1. 找到当前子树的根节点（后序数组的最后一个元素）
    const rootVal = postorder[postorderEnd];
    const root = new TreeNode(rootVal);

    // 2. 找到根节点在中序数组中的索引，划分左右子树区间
    const rootIndex = map.get(rootVal)!; // 题目保证输入有效，非null

    // 3. 计算左子树的节点个数，用于划分后序数组区间
    const leftSize = rootIndex - inorderStart;

    // 4. 递归构造左子树和右子树，赋值给根节点
    // 左子树：中序[start, rootIndex-1]，后序[start, start+leftSize-1]
    root.left = helper(inorderStart, rootIndex - 1, postorderStart, postorderStart + leftSize - 1);
    // 右子树：中序[rootIndex+1, end]，后序[start+leftSize, end-1]
    root.right = helper(rootIndex + 1, inorderEnd, postorderStart + leftSize, postorderEnd - 1);

    // 返回当前子树的根节点
    return root;
  }

  // 初始调用：区间为两个数组的完整区间
  return helper(0, inorder.length - 1, 0, postorder.length - 1);
};

四、代码逐行解析（重点+避坑）

很多新手能看懂思路，但写代码时容易在「区间边界」上出错，这里逐行拆解关键部分，帮大家避坑：

1. 哈希表初始化

const map = new Map<number, number>();
inorder.forEach((val, index) => {
  map.set(val, index);
});

作用：提前缓存中序数组的元素和对应索引，后续每次找根节点索引都能直接通过 map.get(rootVal) 获取，避免重复遍历中序数组，降低时间复杂度。

2. 递归辅助函数（helper）

为什么需要辅助函数？因为我们需要通过「区间边界」来划分左右子树，而主函数的参数只有两个数组，无法直接传递区间信息，所以用 helper 函数封装区间参数，实现递归。

3. 递归终止条件

if (inorderStart > inorderEnd || postorderStart > postorderEnd) {
  return null;
}

避坑点：当区间的起始索引大于结束索引时，说明当前区间没有节点，直接返回 null（比如左子树为空或右子树为空的情况）。比如，根节点的左子树如果没有节点，那么 inorderStart 会等于 rootIndex，此时 inorderStart > rootIndex - 1，触发终止条件，返回 null，正好对应 root.left = null。

4. 根节点创建

const rootVal = postorder[postorderEnd];
const root = new TreeNode(rootVal);

核心：后序遍历的最后一个元素就是当前子树的根节点，这是整个解题的突破口，必须牢记。

5. 区间划分（最容易出错的地方）

const leftSize = rootIndex - inorderStart;
// 左子树递归调用
root.left = helper(inorderStart, rootIndex - 1, postorderStart, postorderStart + leftSize - 1);
// 右子树递归调用
root.right = helper(rootIndex + 1, inorderEnd, postorderStart + leftSize, postorderEnd - 1);

避坑解析：

  • leftSize 是左子树的节点个数，由「根节点索引 - 中序起始索引」得到，因为中序左子树区间是 [inorderStart, rootIndex - 1]，长度为 rootIndex - inorderStart；

  • 后序左子树区间的结束索引 = 起始索引 + 左子树节点个数 - 1（因为区间是闭区间，比如起始索引0，个数2，区间是[0,1]）；

  • 后序右子树的起始索引 = 左子树结束索引 + 1，结束索引 = 原后序结束索引 - 1（去掉根节点）；

  • 中序右子树区间直接从 rootIndex + 1 开始，到 inorderEnd 结束即可。

五、复杂度分析

  • 时间复杂度：O(n)，n 是二叉树的节点个数。哈希表初始化遍历一次中序数组（O(n)），每个节点被递归处理一次（O(n)），每次索引查询 O(1)；

  • 空间复杂度：O(n)，哈希表存储 n 个元素（O(n)），递归调用栈的深度最坏情况下为 n（比如二叉树退化为链表），整体空间复杂度 O(n)。

六、总结与拓展

核心总结

这道题的本质是「利用遍历序列的特点找根节点 + 分治思想拆分左右子树」，关键在于两点：

  1. 牢记后序最后一个元素是根，中序根节点划分左右子树；

  2. 精准划分两个数组的左右子树区间，避免边界出错（建议多动手画示例，标注区间）。

拓展思考

这道题和 LeetCode 105 题（从前序与中序遍历序列构造二叉树）思路高度一致，只是根节点的位置和区间划分略有不同：

  • 105题（前序+中序）：前序的第一个元素是根节点；

  • 106题（后序+中序）：后序的最后一个元素是根节点。

掌握这两道题，就能轻松应对「遍历序列构造二叉树」的所有同类题型。

LeetCode 100. 相同的树：两种解法（递归+迭代）详解

✇掘金 前端
作者 Wect
2026年2月17日 20:50

LeetCode简单难度的经典二叉树题目——100. 相同的树，这道题虽然难度不高，但非常适合入门二叉树的遍历思想，尤其是递归和迭代两种核心思路的对比练习，新手朋友可以重点看看，老手也可以快速回顾巩固一下。

先简单梳理一下题目要求，避免踩坑：给两棵二叉树的根节点p和q，判断这两棵树是否“相同”。这里的相同有两个核心条件，缺一不可：结构上完全一致，并且对应位置的节点值完全相等。

举个直观的例子：如果p是一棵只有根节点（值为1）的树，q也是只有根节点（值为1），那它们是相同的；但如果p的根节点是1、左孩子是2，q的根节点是1、右孩子是2，哪怕节点值都一样，结构不同，也不算相同。

一、题目前置准备

题目已经给出了二叉树节点的定义，用TypeScript实现的，这里再贴一遍，方便大家对照代码理解（注释已补充，新手可重点看构造函数的逻辑）：

class TreeNode {
  val: number; // 节点值
  left: TreeNode | null; // 左孩子，可能为null（没有左孩子）
  right: TreeNode | null; // 右孩子，可能为null（没有右孩子）
  // 构造函数：初始化节点，val默认0，左右孩子默认null
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = (val === undefined ? 0 : val); // 节点值为空时，默认设为0
    this.left = (left === undefined ? null : left); // 左孩子为空时，默认设为null
    this.right = (right === undefined ? null : right); // 右孩子为空时，默认设为null
  }
}

二、解法一：递归解法

1. 递归思路分析

递归的核心思想是“分而治之”，把判断两棵大树是否相同，拆解成判断无数个“小问题”——判断当前两个节点是否相同，以及它们的左孩子、右孩子是否分别相同。

递归的终止条件（也是边界情况）很关键，分三步判断，逻辑层层递进：

  • 如果p和q都为null（两个节点都不存在）：说明这两个位置的节点是相同的，返回true；

  • 如果p和q中一个为null、另一个不为null（一个节点存在，一个不存在）：说明结构不同，返回false；

  • 如果p和q都不为null，但它们的val不相等（节点值不同）：说明节点不相同，返回false；

如果以上三种情况都不满足，说明当前两个节点是相同的，接下来就递归判断它们的左孩子（p.left和q.left）和右孩子（p.right和q.right），只有左右孩子都相同，整棵树才相同（用&&连接两个递归结果）。

2. 递归代码实现

// 递归解法：isSameTree_1
function isSameTree_1(p: TreeNode | null, q: TreeNode | null): boolean {
  // 边界情况1：两个节点都为空，相同
  if (p === null && q === null) {
    return true;
  }
  // 边界情况2：一个为空，一个不为空，结构不同，不相同
  if (p === null || q === null) {
    return false;
  }
  // 边界情况3：两个节点都不为空，但值不同，不相同
  if (p.val !== q.val) {
    return false;
  }
  // 递归：当前节点相同，判断左孩子和右孩子是否都相同
  return isSameTree_1(p.left, q.left) && isSameTree_1(p.right, q.right);
};

3. 递归解法总结

优点：代码极度简洁，逻辑清晰，完全贴合二叉树的递归特性，容易理解和编写，新手友好；

缺点：递归依赖调用栈，如果二叉树深度极深（比如链式二叉树），可能会出现栈溢出的情况（但LeetCode的测试用例一般不会卡这种极端情况，日常刷题完全够用）；

时间复杂度：O(n)，n是两棵树中节点数较少的那一个，每个节点只会被访问一次；

空间复杂度：O(h)，h是树的高度，最坏情况下（链式树）h=n，最好情况下（平衡树）h=logn。

三、解法二：迭代解法（用栈模拟递归，避免栈溢出）

1. 迭代思路分析

迭代解法的核心是“用栈模拟递归的调用过程”，通过手动维护一个栈，把需要判断的节点对（p的节点和q的对应节点）压入栈中，然后循环弹出节点对进行判断，本质上和递归的逻辑是一致的，只是实现方式不同。

具体步骤：

  1. 先判断两棵树的根节点是否都为空（和递归边界1一致），如果是，直接返回true；

  2. 如果根节点一个为空、一个不为空（和递归边界2一致），直接返回false；

  3. 初始化一个栈，把根节点对（p和q）压入栈中（注意压入顺序，后续弹出时要对应）；

  4. 循环：只要栈不为空，就弹出两个节点（pNode和qNode），进行判断；

  5. 判断弹出的两个节点：如果都为空，跳过（继续判断下一组节点）；如果一个为空一个不为空，返回false；如果值不相等，返回false；

  6. 如果当前节点对相同，就把它们的左孩子对、右孩子对依次压入栈中（注意压入顺序，先压右孩子，再压左孩子，因为栈是“后进先出”，和递归的顺序保持一致）；

  7. 循环结束后，说明所有节点对都判断完毕，没有发现不相同的情况，返回true。

这里有个小细节：压入栈的顺序是“p.left、q.left、p.right、q.right”，弹出的时候会先弹出p.right和q.right，再弹出p.left和q.left，和递归时“先判断左孩子，再判断右孩子”的顺序是一致的，不影响结果，但要注意保持对应关系，不能压混。

2. 迭代代码实现

// 迭代解法：isSameTree_2（栈模拟递归）
function isSameTree_2(p: TreeNode | null, q: TreeNode | null): boolean {
  // 先处理根节点的边界情况（和递归一致）
  if (p === null && q === null) {
    return true;
  }
  if (p === null || q === null) {
    return false;
  }
  // 初始化栈，压入根节点对（p和q）
  let stack: (TreeNode | null)[] = [];
  stack.push(p);
  stack.push(q);
  
  // 循环：栈不为空时，持续判断节点对
  while (stack.length > 0) {
    // 弹出两个节点，注意栈是后进先出，所以先弹出q，再弹出p（对应压入顺序）
    let qNode: TreeNode | null = stack.pop() ?? null;
    let pNode: TreeNode | null = stack.pop() ?? null;
    
    // 两个节点都为空，跳过（继续判断下一组）
    if (pNode === null && qNode === null) {
      continue;
    }
    // 一个为空一个不为空，结构不同，返回false
    if (pNode === null || qNode === null) {
      return false;
    }
    // 节点值不同，返回false
    if (pNode.val !== qNode.val) {
      return false;
    }
    
    // 当前节点对相同，压入它们的左孩子对和右孩子对（保持对应关系）
    stack.push(pNode.left);
    stack.push(qNode.left);
    stack.push(pNode.right);
    stack.push(qNode.right);
  }
  
  // 所有节点对都判断完毕，没有不相同的情况，返回true
  return true;
}

3. 迭代解法总结

优点：不依赖递归调用栈，避免了极端情况下的栈溢出问题，稳定性更好；

缺点：代码比递归稍长，需要手动维护栈和循环逻辑，对新手来说稍微复杂一点；

时间复杂度：O(n)，和递归一致，每个节点只会被压入栈、弹出栈各一次，访问一次；

空间复杂度：O(n)，最坏情况下（平衡树），栈中会存储n/2个节点对，空间复杂度为O(n)；最好情况下（链式树），栈中最多存储2个节点对，空间复杂度为O(1)。

四、两种解法对比 & 刷题建议

解法类型 优点 缺点 适用场景
递归 代码简洁、逻辑清晰、易编写 极端情况下可能栈溢出 日常刷题、二叉树深度不深的场景
迭代（栈） 无栈溢出问题、稳定性好 代码稍长、需维护栈逻辑 二叉树深度极深、生产环境场景

刷题建议：新手先掌握递归解法，因为它最贴合二叉树的特性，后续做二叉树的遍历、对称树、翻转树等题目时，思路可以无缝迁移；掌握递归后，再理解迭代解法，重点体会“栈模拟递归”的思想，这是二叉树迭代题目的核心套路。

五、常见踩坑点提醒

  • 踩坑点1：忽略“结构不同”的情况，只判断节点值。比如p有左孩子、q没有左孩子，但其他节点值都相同，此时会误判为相同；

  • 踩坑点2：递归时忘记写终止条件，导致无限递归，栈溢出；

  • 踩坑点3：迭代时压入栈的节点对顺序混乱，导致弹出时判断的不是“对应节点”（比如把p.left和q.right压在一起）；

  • 踩坑点4：处理节点为null时不严谨，比如用p.val === q.val时，没有先判断p和q是否为null，导致空指针错误（代码中已规避此问题）。

六、总结

LeetCode 100. 相同的树，本质上是二叉树“同步遍历”的入门练习，核心是判断“结构+节点值”是否双匹配。递归解法胜在简洁，迭代解法胜在稳定，两种解法的逻辑完全一致，只是实现方式不同。

刷这道题的重点不在于“写出代码”，而在于理解“如何同步判断两棵树的对应节点”，这个思路后续会用到很多类似题目中（比如101. 对称二叉树，只是判断的是“自身的左孩子和右孩子”，逻辑高度相似）。

LeetCode 104. 二叉树的最大深度：解题思路+代码解析

✇掘金 前端
作者 Wect
2026年2月17日 18:29

LeetCode基础题第104题「二叉树的最大深度」，这道题是二叉树遍历的经典入门题，核心考察对二叉树层次遍历（BFS）的理解和应用，适合新手入门练手。今天就来详细拆解这道题，从题目理解到代码实现，再到细节优化，一步步讲清楚，看完就能轻松掌握。

一、题目解读

题目描述

给定一个二叉树 root ，返回其最大深度。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。

简单来说，就是要找到二叉树“最深”的那一层，统计从根到这一层的所有节点个数。举个例子：

  • 如果二叉树只有根节点，没有左右子节点，最大深度就是1；

  • 如果根节点有左子节点，左子节点又有一个子节点，那么最大深度就是3；

  • 如果二叉树是空树（root为null），最大深度就是0。

核心考点

这道题的核心是「二叉树的遍历」，常见的解法有两种：

  1. 层次遍历（BFS，广度优先搜索）：按层遍历二叉树，每遍历完一层，深度加1，最终的深度就是最大深度（本文重点讲解这种解法，对应给出的代码）；

  2. 深度优先搜索（DFS）：递归遍历左右子树，取左右子树的最大深度，再加上当前根节点的深度1，即为整个树的最大深度（后续会补充备选代码）。

二、代码解析（TypeScript）

先贴出完整代码（已优化，解决原代码潜在问题），再逐行拆解思路，新手也能看懂～

/**
 * Definition for a binary tree node.
 * 二叉树节点的定义（题目已给出，无需修改）
 */
class TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = (val === undefined ? 0 : val)
    this.left = (left === undefined ? null : left)
    this.right = (right === undefined ? null : right)
  }
}

/**
 * 计算二叉树最大深度（层次遍历/BFS解法）
 * @param root 二叉树根节点
 * @returns 二叉树的最大深度
 */
function maxDepth(root: TreeNode | null): number {
  // 边界处理：空树直接返回深度0（避免后续无效循环）
  if (root === null) {
    return 0;
  }

  let depth = 0; // 记录当前深度，初始化为0
  // 用数组模拟队列，存储当前层的所有节点（初始存入根节点）
  const queue: TreeNode[] = [root];

  // 队列不为空，说明还有节点未遍历，继续循环
  while (queue.length > 0) {
    const levelSize = queue.length; // 当前层的节点个数
    // 遍历当前层的所有节点
    for (let i = 0; i < levelSize; i++) {
      // 取出当前层的节点（优化：用pop+unshift替代shift，提升性能）
      const node = queue.pop()!;
      
      // 若当前节点有右子节点，存入队列（先存右，再存左，保证遍历顺序）
      if (node.right) {
        queue.unshift(node.right);
      }
      // 若当前节点有左子节点，存入队列
      if (node.left) {
        queue.unshift(node.left);
      }
    }
    // 可选：打印队列，观察每一层遍历后的节点变化（调试用）
    
    
    // 当前层遍历完毕，深度加1
    depth++;
  }

  return depth;
}

逐行拆解思路

1. 边界处理（关键！）

if (root === null) { return 0; }

这一步是很多新手容易忽略的点：如果二叉树是空树（root为null），没有任何节点，最大深度自然是0。如果不做这个判断，后续队列会存入null，导致循环多执行一次，最终返回错误的深度1。

2. 初始化变量

  • let depth = 0;：用于记录二叉树的深度，初始值为0（因为还未开始遍历任何一层）；

  • const queue: TreeNode[] = [root];：用数组模拟队列（队列是BFS的核心数据结构），初始时将根节点存入队列，代表从根节点开始遍历。

3. 层次遍历核心循环

while (queue.length > 0) { ... }：队列不为空，说明还有节点未遍历，循环继续。每一次循环，都代表遍历完「一层」节点。

4. 遍历当前层节点

const levelSize = queue.length;：获取当前层的节点个数，这个值是固定的（因为后续队列会存入下一层的节点，不能直接用queue.length判断当前层节点数）。

for (let i = 0; i < levelSize; i++) { ... }：循环遍历当前层的每一个节点，把每个节点的左右子节点（如果有的话）存入队列，为下一层遍历做准备。

5. 节点取出与子节点入队（性能优化点）

原代码中如果用queue.shift()取出节点，会有性能问题——因为数组的shift()方法是O(n)时间复杂度（需要将数组中所有元素向前移动一位），当二叉树节点较多时，效率会很低。

优化方案：用queue.pop()（O(1)时间复杂度）取出队列尾部的节点，同时调整子节点入队顺序（先存右子节点，再存左子节点），保证遍历顺序和shift()一致，既提升性能，又不影响结果。

这里的!是非空断言，因为我们已经通过边界处理和循环条件，确保队列中的节点一定是TreeNode类型（不会为null），所以可以安全使用非空断言。

6. 深度递增

depth++;：每遍历完一层，说明二叉树的深度增加了1，所以深度加1。当循环结束时，depth就是二叉树的最大深度。

三、代码优化说明

对比LeetCode题目给出的初始模板，这段代码做了3个关键优化，兼顾性能和正确性：

  1. 新增边界处理：解决空树返回错误深度的问题，让代码更健壮；

  2. 性能优化：用pop() + unshift()替代shift()，将节点取出操作的时间复杂度从O(n)降至O(1)，适合处理节点较多的二叉树；

可读性优化：添加详细注释，变量命名语义化（如levelSize代表当前层节点数），方便新手理解每一步的执行过程。

四、备选解法（DFS递归版）

除了上述层次遍历（BFS）解法，这道题还可以用深度优先搜索（DFS）的递归写法，代码更简洁，适合树深度不大的场景（避免递归栈溢出），新手也可以了解一下：

function maxDepthRecursive(root: TreeNode | null): number {
  // 空树返回0
  if (root === null) {
    return 0;
  }
  // 递归计算左右子树的最大深度，当前深度 = 左右子树最大深度 + 1（当前节点）
  return Math.max(maxDepthRecursive(root.left), maxDepthRecursive(root.right)) + 1;
}

递归解法的核心思路：二叉树的最大深度 = 左子树最大深度和右子树最大深度的最大值 + 1（当前根节点），本质是遍历到最底层的叶子节点，再回溯计算深度。

五、总结

LeetCode 104题是二叉树遍历的入门题，难度简单，但能很好地巩固BFS和DFS的基础思路。本文讲解的层次遍历（BFS）解法，适合所有场景（包括极深的二叉树，避免递归栈溢出），优化后的代码兼顾性能和可读性，新手可以重点掌握。

解题关键记住两点：

  1. 边界处理：空树直接返回0，避免错误；

  2. 层次遍历核心：用队列存储每一层的节点，每遍历完一层，深度加1。

❌
❌