难度 - >
简单
日期 - >
2021年4月25日
开始时间 - >
07:57
结束时间 - >
20:06
所用时间 - >
10分钟
执行用时 - >
00 ms
内存消耗 - >
36.0 MB
给你一棵二叉搜索树,请你 按中序遍历 将其重新排列为一棵递增顺序搜索树,使树中最左边的节点成为树的根节点,并且每个节点没有左子节点,只有一个右子节点。
示例 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
import java.util.ArrayList;
import java.util.List;
/**
* 解决方案
* @author HCY
* @since 2021/4/25 7:59 下午
*/
public class Solution {
/**
* 递增顺序搜索树
* @author HCY
* @since 2021/4/25 7:59 下午
* @param root: 树节点
* @return com.algorithm.year2021.a1April.b20TwentyOne.code.TreeNode
*/
public TreeNode increasingBST(TreeNode root) {
List<TreeNode> list = new ArrayList<>();
dfs(root,list);
TreeNode dummy = new TreeNode(-1);
TreeNode cur = dummy;
for (TreeNode node : list) {
cur.right = node;
node.left = null;
cur = node;
}
return dummy.right;
}
private void dfs(TreeNode root, List<TreeNode> list) {
if (root == null){ return; }
dfs(root.left,list);
list.add(root);
dfs(root.right,list);
}
}