☰

企业官网建设流程全解析

首页 / 建站日记 / 企业官网建设流程全解析
二叉搜索树修剪（Trim a Binary Search Tree）：leetcode1 仓库中的 DFS 与迭代解法全解析
2026/9/19 2:13:03 网站建设 项目流程

二叉搜索树修剪（Trim a Binary Search Tree）：leetcode1 仓库中的 DFS 与迭代解法全解析

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本篇指南以 LeetCode 669（Trim a Binary Search Tree，二叉搜索树修剪）为核心，结合当前仓库 leetcode1/leetcode 中python、go、java、javascript、kotlin、typescript等多语言的 0669-trim-a-binary-search-tree 实现，系统讲解如何利用 BST 的有序性，将树中所有节点裁剪到[low, high]区间内。读完你将掌握递归 DFS、显式栈迭代、双线性扫描三种解法，并理解它们的正确性依据、复杂度差异与常见陷阱。

前置知识

开始前，需要熟悉以下基础：

  • 二叉搜索树（BST）性质：左子树所有节点值小于根节点，右子树所有节点值大于根节点。这一有序性决定了"修剪时往哪个方向走"的决策依据——当根节点超界时，可以一次性丢弃整棵子树而无需逐个检查。
  • 递归与 DFS：能够以递归方式遍历树，并在遍历过程中重建树结构（先裁剪子树、再挂接结果）。
  • 树节点的指针操作：通过重新赋值left/right指针修改父子关系，例如把越界的左孩子替换为其右孩子。

仓库中多语言实现统一使用 LeetCode 标准TreeNode定义，例如 python/0669-trim-a-binary-search-tree.py：

# 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

1. 深度优先搜索（递归 DFS）

核心直觉

BST 性质给出了一个非常强力的剪枝策略：

  • 若当前节点值大于high，那么该节点及其整棵右子树都过大，应当整体丢弃，只保留并返回修剪后的左子树；
  • 若当前节点值小于low，那么该节点及其整棵左子树都过小，只保留并返回修剪后的右子树；
  • 若节点值落在[low, high]内，则递归修剪左右孩子，把结果重新挂回当前节点后返回。

算法步骤

  1. 当前节点为null，返回null（递归基）。
  2. 节点值大于high：返回对左子树递归修剪的结果（丢弃当前节点与右子树）。
  3. 节点值小于low：返回对右子树递归修剪的结果（丢弃当前节点与左子树）。
  4. 否则节点在区间内：递归修剪左右孩子，重新挂接后返回该节点。

多语言实现

Python（与仓库实现一致）：

class Solution: def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]: if not root: return None if root.val > high: return self.trimBST(root.left, low, high) if root.val < low: return self.trimBST(root.right, low, high) root.left = self.trimBST(root.left, low, high) root.right = self.trimBST(root.right, low, high) return root

Go（见 go/0669-trim-a-binary-search-tree.go）：

func trimBST(root *TreeNode, low int, high int) *TreeNode { if root == nil { return nil } if root.Val > high { return trimBST(root.Left, low, high) } if root.Val < low { return trimBST(root.Right, low, high) } root.Left = trimBST(root.Left, low, high) root.Right = trimBST(root.Right, low, high) return root }

JavaScript（见 javascript/0669-trim-a-binary-search-tree.js）：

var trimBST = function (root, low, high) { if (!root) { return null; } if (root.val < low) { return trimBST(root.right, low, high); } if (root.val > high) { return trimBST(root.left, low, high); } root.left = trimBST(root.left, low, high); root.right = trimBST(root.right, low, high); return root; };

Java（见 java/0669-trim-a-binary-search-tree.java）：

public class Solution { public TreeNode trimBST(TreeNode root, int low, int high) { if (root == null) { return null; } if (root.val > high) { return trimBST(root.left, low, high); } if (root.val < low) { return trimBST(root.right, low, high); } root.left = trimBST(root.left, low, high); root.right = trimBST(root.right, low, high); return root; } }

C++：

class Solution { public: TreeNode* trimBST(TreeNode* root, int low, int high) { if (!root) return nullptr; if (root->val > high) { return trimBST(root->left, low, high); } if (root->val < low) { return trimBST(root->right, low, high); } root->left = trimBST(root->left, low, high); root->right = trimBST(root->right, low, high); return root; } };

Kotlin、Swift、Rust 的实现与上述逻辑完全同构（注意 Rust 版需通过Rc<RefCell<TreeNode>>借用检查，先取left/right的克隆再写回），见仓库对应的 kotlin/0669-trim-a-binary-search-tree.kt 与 typescript/0669-trim-a-binary-search-tree.ts。

复杂度

  • 时间复杂度：$O(n)$，每个节点最多被访问一次。
  • 空间复杂度：$O(n)$，最坏情况下（如链状树）递归栈深度为 $n$。

2. 迭代 DFS（显式栈）

核心直觉

递归可以借助显式栈改写为迭代。整体思路不变：越界节点需要被其合法的孩子替换。与递归"自顶向下一次性返回结果"不同，迭代法先找到合法的根节点，再借助栈逐层修复越界孩子——通过把越界孩子替换为其合适的孙节点来"跳级"接续。

算法步骤

  1. 寻找合法根：若当前根过小则走向右孩子，过大则走向左孩子，直到根落在[low, high]内。
  2. 用该合法根初始化栈。
  3. 当栈非空时循环：
    • 弹出节点node；
    • 若左孩子存在且值小于low，将其替换为左孩子的右孩子；
    • 若右孩子存在且值大于high，将其替换为右孩子的左孩子；
    • 若发生了替换，把node重新压栈（因为替换上来的孙节点可能仍越界，需要再次检查）；
    • 否则把左右孩子（若存在）压栈继续处理。
  4. 返回合法根。

多语言实现

Python：

class Solution: def trimBST(self, root, low, high): while root and (root.val < low or root.val > high): if root.val < low: root = root.right else: root = root.left stack = [root] while stack: node = stack.pop() if not node: continue left_out = node.left and node.left.val < low right_out = node.right and node.right.val > high if left_out: node.left = node.left.right if right_out: node.right = node.right.left if left_out or right_out: stack.append(node) else: if node.left: stack.append(node.left) if node.right: stack.append(node.right) return root

Java：

public class Solution { public TreeNode trimBST(TreeNode root, int low, int high) { while (root != null && (root.val < low || root.val > high)) { root = (root.val < low) ? root.right : root.left; } Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); if (node == null) continue; boolean leftOut = (node.left != null && node.left.val < low); boolean rightOut = (node.right != null && node.right.val > high); if (leftOut) node.left = node.left.right; if (rightOut) node.right = node.right.left; if (leftOut || rightOut) { stack.push(node); } else { if (node.left != null) stack.push(node.left); if (node.right != null) stack.push(node.right); } } return root; } }

C++：

class Solution { public: TreeNode* trimBST(TreeNode* root, int low, int high) { while (root && (root->val < low || root->val > high)) { root = (root->val < low) ? root->right : root->left; } stack<TreeNode*> stack; stack.push(root); while (!stack.empty()) { TreeNode* node = stack.top(); stack.pop(); if (!node) continue; bool leftOut = (node->left && node->left->val < low); bool rightOut = (node->right && node->right->val > high); if (leftOut) node->left = node->left->right; if (rightOut) node->right = node->right->left; if (leftOut || rightOut) { stack.push(node); } else { if (node->left) stack.push(node->left); if (node->right) stack.push(node->right); } } return root; } };

JavaScript、Go、Kotlin、Swift、Rust 版本结构一致，其中 Rust 版用Vec<Option<Rc<RefCell<TreeNode>>>>作为栈，并在替换越界孩子时先clone()出孙节点引用再写回，避免借用冲突。

复杂度

  • 时间复杂度：$O(n)$。
  • 空间复杂度：$O(n)$（栈空间）。

3. 迭代 DFS（最优版：双线性扫描）

核心直觉

显式栈仍然需要 $O(n)$ 的辅助空间。利用 BST 的偏序特性，可以进一步去掉栈：找到合法根之后，沿左脊线向下修复所有小于low的节点，再沿右脊线向下修复所有大于high的节点。原因在于 BST 中一旦在某一侧修复了一个节点，只需要继续沿同一方向检查即可——左子树中不可能存在"需要修右边界"的节点（所有左子树节点都更小），反之亦然。

算法步骤

  1. 跳过越界节点，找到合法的根。
  2. 用tmpRoot保存该合法根。
  3. 左脊线：只要左孩子存在且值小于low，就把它替换为左孩子的右孩子；随后下移到新的左孩子，重复直到左孩子合法或为空。
  4. 回到tmpRoot，右脊线：只要右孩子存在且值大于high，就把它替换为右孩子的左孩子；随后下移到新的右孩子，重复。
  5. 返回tmpRoot。

多语言实现

Python：

class Solution: def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]: while root and (root.val < low or root.val > high): root = root.right if root.val < low else root.left tmpRoot = root while root: while root.left and root.left.val < low: root.left = root.left.right root = root.left root = tmpRoot while root: while root.right and root.right.val > high: root.right = root.right.left root = root.right return tmpRoot

Java：

public class Solution { public TreeNode trimBST(TreeNode root, int low, int high) { while (root != null && (root.val < low || root.val > high)) { root = (root.val < low) ? root.right : root.left; } TreeNode tmpRoot = root; while (root != null) { while (root.left != null && root.left.val < low) { root.left = root.left.right; } root = root.left; } root = tmpRoot; while (root != null) { while (root.right != null && root.right.val > high) { root.right = root.right.left; } root = root.right; } return tmpRoot; } }

C++：

class Solution { public: TreeNode* trimBST(TreeNode* root, int low, int high) { while (root && (root->val < low || root->val > high)) { root = (root->val < low) ? root->right : root->left; } TreeNode* tmpRoot = root; while (root) { while (root->left && root->left->val < low) { root->left = root->left->right; } root = root->left; } root = tmpRoot; while (root) { while (root->right && root->right->val > high) { root->right = root->right->left; } root = root->right; } return tmpRoot; } };

JavaScript、Go、Kotlin、Swift、Rust 版本逻辑相同；Rust 版通过loop { ... match ... _ => break }模拟内层 while 循环，并配合borrow()/borrow_mut()交替读写节点字段。

复杂度

  • 时间复杂度：$O(n)$。
  • 空间复杂度：$O(1)$ 额外空间（不使用递归栈或显式栈），是三种写法中最省内存的。

常见陷阱

陷阱一：跳过越界节点后忘记继续递归修剪

当某节点值越界、跳到其合法方向的孩子时，必须继续对该孩子子树做修剪。常见错误是直接返回该孩子而不递归处理——这个孩子本身或其子孙仍可能越界。例如递归版中return self.trimBST(root.left, low, high)必须带上前缀递归调用，而非return root.left。

陷阱二：混淆越界时应保留哪一侧子树

  • 节点值大于high：应返回修剪后的左子树（不是右子树）；
  • 节点值小于low：应返回修剪后的右子树（不是左子树）。

把这两者搞反会违反 BST 性质，得到错误结果。判断依据很简单：low是下界，小于low的节点连同其左子树（全部更小）都应被舍弃，唯一可能合法的是右子树；high是上界，同理。

陷阱三：未处理根节点本身越界的情况

根节点可能不在[low, high]区间内，此时整个原始根都会被丢弃，需要先在子树中找到新的合法根。常见疏漏是假设根一定合法。无论递归还是迭代解法，都必须先处理"根越界"：递归版通过root.val > high/root.val < low两个分支自然下沉；迭代版则在主循环之前用 while 循环跳到合法根（见第 2、3 节的步骤 1）。

总结

解法思路时间复杂度空间复杂度适用场景
递归 DFS后序重建，越界即丢整侧子树$O(n)$$O(n)$（递归栈）最直观、面试首选
迭代 DFS（栈）先找合法根，再逐层替换越界孩子$O(n)$$O(n)$（显式栈）避免递归深度限制
迭代 DFS（双脊线）左脊修下界、右脊修上界$O(n)$$O(1)$追求常数辅助空间

三种解法的正确性都建立在 BST"左小右大"的性质上：越界时整棵子树可以直接丢弃，使得修剪只需沿少数路径下沉，而非遍历所有节点。仓库中的 0669-trim-a-binary-search-tree 系列实现覆盖 Python、Go、Java、JavaScript、Kotlin、TypeScript 六种语言，逻辑与本文讲解的递归 DFS 完全一致，可作为复习或对照调试的参考。递归版最适合快速 AC，最优迭代版则适合在空间受限场景或需要展示工程化能力时使用。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

标签： 网站建设 企业官网 项目流程 UI设计 前端开发

热门文章

文章分类

标签云

网站建设 响应式设计 用户体验 SEO优化 前端开发 小程序 电商平台 性能优化

相关文章

您可能感兴趣的其他内容

图书管理系统面向对象分析与设计实战：从用例图到状态机
2026/9/19 2:13:02 网站建设

图书管理系统面向对象分析与设计实战：从用例图到状态机

简介&#xff1a;这份图书管理系统面向对象分析与设计报告&#xff0c;是软件工程课程设计、系统分析作业及小型信息管理系统开发前的重要参考&#xff0c;适合正在学习UML建模、需要撰写课程报告或启动图书馆相关项目的学生与开发者。报告围绕系统管理员、图书管理员、读者三个…...

阅读更多 →
基于Python的个性化学习路径生成系统设计与实现
2026/9/19 2:12:31 网站建设

基于Python的个性化学习路径生成系统设计与实现

你有没有遇到过这种情况&#xff1a;同样一门Python课&#xff0c;有的人两周就上手了&#xff0c;有的人学了一个月还在循环语句里打转&#xff1b;有人靠看视频学得飞快&#xff0c;有人非要手敲代码才有感觉。问题不全在个人努力&#xff0c;更在于——所有人拿到的是同一条…...

阅读更多 →
APS生产计划培训手册：有限产能排产调度核心逻辑
2026/9/19 2:10:00 网站建设

APS生产计划培训手册：有限产能排产调度核心逻辑

简介&#xff1a;面向制造业生产计划与供应链管理人员的APS生产计划培训手册&#xff0c;以Hitachi Consulting的ASCP高级计划排程模块为主线&#xff0c;系统讲解从需求整理、数据准备、计划制定到结果分析与工单下达的完整业务闭环。手册包含ASCP业务流与数据流总览、计划参数…...

阅读更多 →

需要专业的网站建设服务？

联系我们获取免费的网站建设咨询和方案报价，让我们帮助您实现业务目标

立即咨询