897. 递增顺序查找树 #
Difficulty: 简单
给你一个树，请你 按中序遍历 重新排列树，使树中最左边的结点现在是树的根，并且每个结点没有左子结点，只有一个右子结点。
示例 ：
输入：[5,3,6,2,4,null,8,1,null,null,null,7,9]
5
/ \
3 6
/ \ \
2 4 8
/ / \
1 7 9
输出：[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和100之间。 - 每个结点都有一个从
0到1000范围内的唯一整数值。
题解 #
解法一：中序遍历 + 构造新的树 #
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode increasingBST(TreeNode root) {
List<Integer> list = new ArrayList<>();
inOrder(root, list);
TreeNode node = new TreeNode(0);
TreeNode cur = node;
for (int v : list) {
cur.right = new TreeNode(v);
cur = cur.right;
}
return node.right;
}
private void inOrder(TreeNode node, List<Integer> list) {
if (node == null) {
return;
}
inOrder(node.left, list);
list.add(node.val);
inOrder(node.right, list);
}
}
复杂度分析 #
-
时间复杂度：O(N)，其中 N 是树上的节点个数。
-
空间复杂度：O(N)。
解法二：中序遍历 + 更改树的连接方式 #
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
TreeNode cur;
public TreeNode increasingBST(TreeNode root) {
TreeNode ans = new TreeNode(0);
cur = ans;
inorder(root);
return ans.right;
}
public void inorder(TreeNode node) {
if (node == null) return;
inorder(node.left);
node.left = null;
cur.right = node;
cur = node;
inorder(node.right);
}
}
复杂度分析 #
-
时间复杂度：O(N)，其中 N 是树上的节点个数。
-
空间复杂度：O(H)，其中 H 是树的高度。