友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
897. 递增顺序搜索树
给你一棵二叉搜索树的 root ，请你 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。
示例 1：
输入：root = [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]
示例 2：
输入：root = [5,1,7] 输出：[1,null,5,null,7]
提示：
-
树中节点数的取值范围是
[1, 100] -
0 <= Node.val <= 1000
思路分析
深度优先遍历。直接在深度优先遍历的时候，把指针改掉的解法，还要多思考一下。另外，也可以思考一下 Morris 遍历解法。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-09-05 21:58:39
*/
public TreeNode increasingBST(TreeNode root) {
List<TreeNode> list = new ArrayList<>();
dfs(root, list);
TreeNode result = list.getFirst();
TreeNode pre = null;
for (int i = 0; i < list.size(); i++) {
TreeNode node = list.get(i);
node.left = null;
node.right = null;
if(pre != null) {
pre.right = node;
}
pre = node;
}
return result;
}
private void dfs(TreeNode root, List<TreeNode> list) {
if (root == null) {
return;
}
dfs(root.left, list);
list.add(root);
dfs(root.right, list);
}