剑指 Offer II 052. 展平二叉搜索树

题目

给你一棵二叉搜索树,请 按中序遍历 将其重新排列为一棵递增顺序搜索树,使树中最左边的节点成为树的根节点,并且每个节点没有左子节点,只有一个右子节点。

示例1:

1
2
输入: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:

1
2
输入:root = [5,1,7]
输出:[1,null,5,null,7]

提示:

  • 树中节点数的取值范围是 [1, 100]
  • 0 <= Node.val <= 1000

解法一:

JAVA

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
public TreeNode increasingBST(TreeNode root) {
if (Objects.isNull(root)) {
return null;
}
List<Integer> tree = new ArrayList<>();
travel(root, tree);
root.val = tree.get(0);
root.right = null;
root.left = null;
TreeNode pre = root;
for (int i = 1;i < tree.size();i++) {
TreeNode treeNode = new TreeNode(tree.get(i));
pre.right = treeNode;
pre = treeNode;
}
return root;
}

private void travel(TreeNode root, List<Integer> tree) {
if (Objects.isNull(root)) {
return;
}

travel(root.left, tree);
tree.add(root.val);
travel(root.right, tree);
}
0%