LeetCode-Go 题解897. Increasing Order Search Tree 递增顺序搜索树中序遍历重组二叉树【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文讲解 LeetCode 第 897 题「Increasing Order Search Tree递增顺序搜索树」在 LeetCode-Go 仓库中的完整解法。该题的核心是把一棵二叉搜索树按中序遍历重新排列成一条只有右孩子的链本文不仅翻译并详解原题题意与示例还基于仓库内 897. Increasing Order Search Tree.go 的两种实现分别剖析中序遍历重建新树与原地重构链表思想两条思路并结合测试文件与公共树结构工具说明其正确性验证方式。读完本文你将掌握二叉搜索树中序遍历在展平/重排类题目中的两种典型应用以及如何在 Go 中通过 tail 指针实现空间优化的原地改写。题目把二叉搜索树拉直成递增链原题描述给定一棵二叉搜索树BST按中序遍历in-order重新排列这棵树使得原树中最左边的结点成为新树的根并且每个结点都没有左子结点只有 1 个右子结点。也就是说最终结果是一棵退化成右链的树沿着这条链从头到尾走一遍正好等于原树的中序遍历序列。示例以题目给出的输入为例Input: [5,3,6,2,4,null,8,1,null,null,null,7,9] 5 / \ 3 6 / \ \ 2 4 8 / / \ 1 7 9 Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9] 1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ 8 \ 9观察可知输出结果在层级遍历数组表示中呈现1, null, 2, null, 3, ...的形态每个结点只有一个右孩子null表示左孩子为空。从数值上看输出的序列恰好是原树中序遍历得到的升序序列1,2,3,4,5,6,7,8,9。约束条件根据 README.md 中的题目说明给定树中的结点数介于1 和 100之间每个结点都有一个从0 到 1000范围内的唯一整数值。由于结点值唯一且范围有限结点的数值天然可以作为中序遍历的有序键这也保证了按值递增串成右链这一结果是确定的。核心思路中序遍历是这一切的基础二叉搜索树有一个基本性质中序遍历左子树 → 根 → 右子树得到的结果一定是升序序列。题目要求的左子树 → 根 → 右子树的重新排列本质就是把中序遍历序列中的每个结点依次挂到前一个结点的右孩子上。因此两种主流解法都建立在先做一次中序遍历之上区别只在于解法二模拟先中序遍历收集结点值再从头新建一棵右链树——思路直观但额外开辟了存储解法一链表思想不新建结点在遍历过程中直接改写原有结点的左右指针把树当作链表就地反转——空间更省。下面依次展开讲解代码均出自仓库 897. Increasing Order Search Tree.go。解法二中序遍历 重建新树模拟思路最直观算法过程对原树做一次中序遍历把结点值依次收集进切片list以list[0]为根新建新树的根结点从list[1]开始逐个创建只有右孩子的新结点挂在当前链尾结点cur的Right上返回新根。源码实现仓库中的实现increasingBST1见 897. Increasing Order Search Tree.go// 解法二 模拟 func increasingBST1(root *TreeNode) *TreeNode { list : []int{} inorder(root, list) if len(list) 0 { return root } newRoot : TreeNode{Val: list[0], Left: nil, Right: nil} cur : newRoot for index : 1; index len(list); index { tmp : TreeNode{Val: list[index], Left: nil, Right: nil} cur.Right tmp cur tmp } return newRoot } func inorder(root *TreeNode, output *[]int) { if root ! nil { inorder(root.Left, output) *output append(*output, root.Val) inorder(root.Right, output) } }配套的中序遍历辅助函数inorder见 897. Increasing Order Search Tree.go采用标准递归写法先递归左子树再把当前结点值追加到输出切片最后递归右子树。注意这里通过*output append(*output, root.Val)修改的是指针指向的切片本身保证递归过程中累积结果不丢失。复杂度分析时间复杂度O(n)。中序遍历每个结点访问一次重建链表时又遍历一次list两次都是线性开销n 为结点总数。空间复杂度O(n)。额外消耗主要来自三处——存储中序序列的切片listO(n)、新建的 n 个结点O(n)、递归调用栈最坏情况下树退化为链时为 O(n)。该解法的缺点是重建意味着放弃了原树的结点对象需要额外分配内存优点则是逻辑简单、不易出错适合作为面试时快速给出的第一版答案。解法一链表思想原地重构空间更优原文档指出树可以看做是有多个孩子的链表这一题可以看成是链表的类似反转的操作。想通这一点后可以不新建任何结点直接在原树上完成重排。关键洞察把每个结点看成链上的一个元素中序遍历的顺序就是这条链的目标顺序维护一个tail指针它始终指向当前已经串好的右链的最后一个结点递归过程中每访问到一个结点就把它接到tail的右侧并把tail更新为该结点由于结点在树中可能还有左孩子在接入右链前必须先把root.Left置为nil否则会形成环或残留左子树引用导致输出错误甚至无限循环。源码实现仓库中的实现increasingBST与recBST见 897. Increasing Order Search Tree.go// 解法一 链表思想 func increasingBST(root *TreeNode) *TreeNode { var head TreeNode{} tail : head recBST(root, tail) return head.Right } func recBST(root, tail *TreeNode) *TreeNode { if root nil { return tail } tail recBST(root.Left, tail) root.Left nil // 切断 root 与其 Left 的连接避免形成环 tail.Right, tail root, root // 把 root 接上 tail并保持 tail 指向尾部 tail recBST(root.Right, tail) return tail }逐行拆解var head TreeNode{}创建一个**哑结点dummy head**作为哨兵head.Right最终指向新右链的第一个结点即原树最左边的结点。用哑结点可以统一链为空与链非空两种情况的代码避免特判。tail : headtail表示当前已串好部分的末尾。初始时链为空末尾就是哑结点本身。recBST(root, tail)的返回值设计recBST接收两个参数——当前子树根root和当前链尾tail返回处理完该子树后新的链尾。这样每一层递归都能把串好的尾部传回给上层继续往后接。递归顺序与中序遍历严格一致先recBST(root.Left, tail)处理左子树把左子树的所有结点先串进右链返回更新后的链尾再root.Left nil切断当前结点与左孩子的连接。因为当前结点马上要作为链的最后一个结点它不应该再保留任何左子树引用然后tail.Right, tail root, root把root接到链尾的右侧同时让tail指向root完成追加结点这一动作。这行代码同时完成了赋值和指针移动是 Go 中多值赋值的典型用法最后recBST(root.Right, tail)处理右子树右子树的所有结点按中序顺序应排在root之后返回最终链尾。最终return head.Right跳过哑结点返回真正的新树根。为什么这样写能保持中序顺序以示例树为例递归的执行顺序是recBST(5, head) recBST(3, head) recBST(2, head) recBST(1, head) → 1 接到链尾链尾变为 1 → 2 接到 1 右侧链尾变为 2 → 3 接到 2 右侧链尾变为 3 recBST(4, 3) → 4 接到 3 右侧链尾变为 4 → 5 接到 4 右侧链尾变为 5 recBST(6, 5) → 6 接到 5 右侧链尾变为 6 recBST(8, 6) recBST(7, 6) → 7 接到 6 右侧链尾变为 7 → 8 接到 7 右侧链尾变为 8 recBST(9, 8) → 9 接到 8 右侧链尾变为 9最终head.Right指向 1链为1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9与原题输出完全一致。可以看到整个过程没有创建任何新结点只是把原有结点的Right指针重新串联这正是树可看作多孩子链表这一思想的具体落地。复杂度分析时间复杂度O(n)。每个结点恰好被访问一次递归遍历 指针重接均为常数操作。空间复杂度O(h)。不依赖额外数据结构和新建结点唯一的额外开销是递归调用栈h 为树高最坏情况下树退化为链为 O(n)平均/平衡情况下为 O(log n)。相比解法二省去了list切片与新建结点的 O(n) 空间。原文档也提醒虽然平时软件开发过程中不建议更改原有的值但算法题中追求空间和时间的最优可以考虑一下——解法一正是这一取舍的体现。树结点结构与测试验证公共 TreeNode 定义两种解法都依赖仓库公共模块structures中的树结点定义。仓库通过类型别名复用该定义见 897. Increasing Order Search Tree.go// TreeNode define type TreeNode structures.TreeNodestructures包中TreeNode的结构见 structures/TreeNode.go// TreeNode is trees node type TreeNode struct { Val int Left *TreeNode Right *TreeNode }测试用例如何构造与校验仓库的测试文件 897. Increasing Order Search Tree_test.go 采用表驱动测试每个用例由para897输入树的层级遍历切片与ans897期望输出链的层级遍历切片组成测试主体Test_Problem897见 测试文件第 27 行起。测试中使用了两个structures提供的工具函数structures.Ints2TreeNode(p.one)把层级遍历的[]int切片还原成二叉树实现见 structures/TreeNode.gostructures.Tree2ints(rootOne)把处理后的树再按层级遍历还原成[]int切片便于与期望输出比对实现见 structures/TreeNode.go。测试数据中的structures.NULL是一个特殊哨兵值-1 63定义见 structures/TreeNode.go用来表示空结点。用例覆盖了题目示例、单结点树、空树、以及多层非平衡树等场景。例如第一个用例输入[5, 3, 6, 2, 4, NULL, 8, 1, NULL, NULL, NULL, 7, 9]期望输出[1, NULL, 2, NULL, 3, NULL, 4, NULL, 5, NULL, 6, NULL, 7, NULL, 8, NULL, 9]与题目示例一一对应同时测试还会依次调用increasingBST与increasingBST1两个解法保证两种实现输出一致。本地运行测试在仓库根目录下执行以下命令即可运行本题测试go test -v -run Test_Problem897 ./leetcode/0897.Increasing-Order-Search-Tree/命令会输出------------------------Leetcode Problem 897------------------------分隔行并依次打印每个用例的输入与处理结果。该测试用例同样依赖仓库 go.mod 中声明的模块路径github.com/halfrost/LeetCode-Go及其子包structures属于仓库自洽的测试体系的一部分。总结第 897 题是一道中序遍历 链表重组的经典应用题LeetCode-Go 仓库给出了两种互补的实现维度解法二模拟解法一链表思想核心动作中序遍历收集值重建右链递归中序串接原地改写指针是否新建结点是否时间复杂度O(n)O(n)空间复杂度O(n)O(h)h 为树高代码位置897. Increasing Order Search Tree.go897. Increasing Order Search Tree.go实际面试与工程实践中解法二适合作为先写对的基线方案而解法一借助树即链表的视角与tail指针技巧在不引入额外存储的前提下完成了中序重组且通过root.Left nil规避了指针环问题更值得反复咀嚼。理解这一题后Morris 遍历等依赖指针重组的树算法思想也会更容易上手因为它们的核心同样是把树的指针关系当作链表关系来操作。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Go 题解：897. Increasing Order Search Tree 递增顺序搜索树（中序遍历重组二叉树）
LeetCode-Go 题解897. Increasing Order Search Tree 递增顺序搜索树中序遍历重组二叉树【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文讲解 LeetCode 第 897 题「Increasing Order Search Tree递增顺序搜索树」在 LeetCode-Go 仓库中的完整解法。该题的核心是把一棵二叉搜索树按中序遍历重新排列成一条只有右孩子的链本文不仅翻译并详解原题题意与示例还基于仓库内 897. Increasing Order Search Tree.go 的两种实现分别剖析中序遍历重建新树与原地重构链表思想两条思路并结合测试文件与公共树结构工具说明其正确性验证方式。读完本文你将掌握二叉搜索树中序遍历在展平/重排类题目中的两种典型应用以及如何在 Go 中通过 tail 指针实现空间优化的原地改写。题目把二叉搜索树拉直成递增链原题描述给定一棵二叉搜索树BST按中序遍历in-order重新排列这棵树使得原树中最左边的结点成为新树的根并且每个结点都没有左子结点只有 1 个右子结点。也就是说最终结果是一棵退化成右链的树沿着这条链从头到尾走一遍正好等于原树的中序遍历序列。示例以题目给出的输入为例Input: [5,3,6,2,4,null,8,1,null,null,null,7,9] 5 / \ 3 6 / \ \ 2 4 8 / / \ 1 7 9 Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9] 1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ 8 \ 9观察可知输出结果在层级遍历数组表示中呈现1, null, 2, null, 3, ...的形态每个结点只有一个右孩子null表示左孩子为空。从数值上看输出的序列恰好是原树中序遍历得到的升序序列1,2,3,4,5,6,7,8,9。约束条件根据 README.md 中的题目说明给定树中的结点数介于1 和 100之间每个结点都有一个从0 到 1000范围内的唯一整数值。由于结点值唯一且范围有限结点的数值天然可以作为中序遍历的有序键这也保证了按值递增串成右链这一结果是确定的。核心思路中序遍历是这一切的基础二叉搜索树有一个基本性质中序遍历左子树 → 根 → 右子树得到的结果一定是升序序列。题目要求的左子树 → 根 → 右子树的重新排列本质就是把中序遍历序列中的每个结点依次挂到前一个结点的右孩子上。因此两种主流解法都建立在先做一次中序遍历之上区别只在于解法二模拟先中序遍历收集结点值再从头新建一棵右链树——思路直观但额外开辟了存储解法一链表思想不新建结点在遍历过程中直接改写原有结点的左右指针把树当作链表就地反转——空间更省。下面依次展开讲解代码均出自仓库 897. Increasing Order Search Tree.go。解法二中序遍历 重建新树模拟思路最直观算法过程对原树做一次中序遍历把结点值依次收集进切片list以list[0]为根新建新树的根结点从list[1]开始逐个创建只有右孩子的新结点挂在当前链尾结点cur的Right上返回新根。源码实现仓库中的实现increasingBST1见 897. Increasing Order Search Tree.go// 解法二 模拟 func increasingBST1(root *TreeNode) *TreeNode { list : []int{} inorder(root, list) if len(list) 0 { return root } newRoot : TreeNode{Val: list[0], Left: nil, Right: nil} cur : newRoot for index : 1; index len(list); index { tmp : TreeNode{Val: list[index], Left: nil, Right: nil} cur.Right tmp cur tmp } return newRoot } func inorder(root *TreeNode, output *[]int) { if root ! nil { inorder(root.Left, output) *output append(*output, root.Val) inorder(root.Right, output) } }配套的中序遍历辅助函数inorder见 897. Increasing Order Search Tree.go采用标准递归写法先递归左子树再把当前结点值追加到输出切片最后递归右子树。注意这里通过*output append(*output, root.Val)修改的是指针指向的切片本身保证递归过程中累积结果不丢失。复杂度分析时间复杂度O(n)。中序遍历每个结点访问一次重建链表时又遍历一次list两次都是线性开销n 为结点总数。空间复杂度O(n)。额外消耗主要来自三处——存储中序序列的切片listO(n)、新建的 n 个结点O(n)、递归调用栈最坏情况下树退化为链时为 O(n)。该解法的缺点是重建意味着放弃了原树的结点对象需要额外分配内存优点则是逻辑简单、不易出错适合作为面试时快速给出的第一版答案。解法一链表思想原地重构空间更优原文档指出树可以看做是有多个孩子的链表这一题可以看成是链表的类似反转的操作。想通这一点后可以不新建任何结点直接在原树上完成重排。关键洞察把每个结点看成链上的一个元素中序遍历的顺序就是这条链的目标顺序维护一个tail指针它始终指向当前已经串好的右链的最后一个结点递归过程中每访问到一个结点就把它接到tail的右侧并把tail更新为该结点由于结点在树中可能还有左孩子在接入右链前必须先把root.Left置为nil否则会形成环或残留左子树引用导致输出错误甚至无限循环。源码实现仓库中的实现increasingBST与recBST见 897. Increasing Order Search Tree.go// 解法一 链表思想 func increasingBST(root *TreeNode) *TreeNode { var head TreeNode{} tail : head recBST(root, tail) return head.Right } func recBST(root, tail *TreeNode) *TreeNode { if root nil { return tail } tail recBST(root.Left, tail) root.Left nil // 切断 root 与其 Left 的连接避免形成环 tail.Right, tail root, root // 把 root 接上 tail并保持 tail 指向尾部 tail recBST(root.Right, tail) return tail }逐行拆解var head TreeNode{}创建一个**哑结点dummy head**作为哨兵head.Right最终指向新右链的第一个结点即原树最左边的结点。用哑结点可以统一链为空与链非空两种情况的代码避免特判。tail : headtail表示当前已串好部分的末尾。初始时链为空末尾就是哑结点本身。recBST(root, tail)的返回值设计recBST接收两个参数——当前子树根root和当前链尾tail返回处理完该子树后新的链尾。这样每一层递归都能把串好的尾部传回给上层继续往后接。递归顺序与中序遍历严格一致先recBST(root.Left, tail)处理左子树把左子树的所有结点先串进右链返回更新后的链尾再root.Left nil切断当前结点与左孩子的连接。因为当前结点马上要作为链的最后一个结点它不应该再保留任何左子树引用然后tail.Right, tail root, root把root接到链尾的右侧同时让tail指向root完成追加结点这一动作。这行代码同时完成了赋值和指针移动是 Go 中多值赋值的典型用法最后recBST(root.Right, tail)处理右子树右子树的所有结点按中序顺序应排在root之后返回最终链尾。最终return head.Right跳过哑结点返回真正的新树根。为什么这样写能保持中序顺序以示例树为例递归的执行顺序是recBST(5, head) recBST(3, head) recBST(2, head) recBST(1, head) → 1 接到链尾链尾变为 1 → 2 接到 1 右侧链尾变为 2 → 3 接到 2 右侧链尾变为 3 recBST(4, 3) → 4 接到 3 右侧链尾变为 4 → 5 接到 4 右侧链尾变为 5 recBST(6, 5) → 6 接到 5 右侧链尾变为 6 recBST(8, 6) recBST(7, 6) → 7 接到 6 右侧链尾变为 7 → 8 接到 7 右侧链尾变为 8 recBST(9, 8) → 9 接到 8 右侧链尾变为 9最终head.Right指向 1链为1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9与原题输出完全一致。可以看到整个过程没有创建任何新结点只是把原有结点的Right指针重新串联这正是树可看作多孩子链表这一思想的具体落地。复杂度分析时间复杂度O(n)。每个结点恰好被访问一次递归遍历 指针重接均为常数操作。空间复杂度O(h)。不依赖额外数据结构和新建结点唯一的额外开销是递归调用栈h 为树高最坏情况下树退化为链为 O(n)平均/平衡情况下为 O(log n)。相比解法二省去了list切片与新建结点的 O(n) 空间。原文档也提醒虽然平时软件开发过程中不建议更改原有的值但算法题中追求空间和时间的最优可以考虑一下——解法一正是这一取舍的体现。树结点结构与测试验证公共 TreeNode 定义两种解法都依赖仓库公共模块structures中的树结点定义。仓库通过类型别名复用该定义见 897. Increasing Order Search Tree.go// TreeNode define type TreeNode structures.TreeNodestructures包中TreeNode的结构见 structures/TreeNode.go// TreeNode is trees node type TreeNode struct { Val int Left *TreeNode Right *TreeNode }测试用例如何构造与校验仓库的测试文件 897. Increasing Order Search Tree_test.go 采用表驱动测试每个用例由para897输入树的层级遍历切片与ans897期望输出链的层级遍历切片组成测试主体Test_Problem897见 测试文件第 27 行起。测试中使用了两个structures提供的工具函数structures.Ints2TreeNode(p.one)把层级遍历的[]int切片还原成二叉树实现见 structures/TreeNode.gostructures.Tree2ints(rootOne)把处理后的树再按层级遍历还原成[]int切片便于与期望输出比对实现见 structures/TreeNode.go。测试数据中的structures.NULL是一个特殊哨兵值-1 63定义见 structures/TreeNode.go用来表示空结点。用例覆盖了题目示例、单结点树、空树、以及多层非平衡树等场景。例如第一个用例输入[5, 3, 6, 2, 4, NULL, 8, 1, NULL, NULL, NULL, 7, 9]期望输出[1, NULL, 2, NULL, 3, NULL, 4, NULL, 5, NULL, 6, NULL, 7, NULL, 8, NULL, 9]与题目示例一一对应同时测试还会依次调用increasingBST与increasingBST1两个解法保证两种实现输出一致。本地运行测试在仓库根目录下执行以下命令即可运行本题测试go test -v -run Test_Problem897 ./leetcode/0897.Increasing-Order-Search-Tree/命令会输出------------------------Leetcode Problem 897------------------------分隔行并依次打印每个用例的输入与处理结果。该测试用例同样依赖仓库 go.mod 中声明的模块路径github.com/halfrost/LeetCode-Go及其子包structures属于仓库自洽的测试体系的一部分。总结第 897 题是一道中序遍历 链表重组的经典应用题LeetCode-Go 仓库给出了两种互补的实现维度解法二模拟解法一链表思想核心动作中序遍历收集值重建右链递归中序串接原地改写指针是否新建结点是否时间复杂度O(n)O(n)空间复杂度O(n)O(h)h 为树高代码位置897. Increasing Order Search Tree.go897. Increasing Order Search Tree.go实际面试与工程实践中解法二适合作为先写对的基线方案而解法一借助树即链表的视角与tail指针技巧在不引入额外存储的前提下完成了中序重组且通过root.Left nil规避了指针环问题更值得反复咀嚼。理解这一题后Morris 遍历等依赖指针重组的树算法思想也会更容易上手因为它们的核心同样是把树的指针关系当作链表关系来操作。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考