897. 递增顺序查找树
给定一个树，按中序遍历重新排列树，使树中最左边的结点现在是树的根，并且每个结点没有左子结点，只有一个右子结点。
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例1:
输入：[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 范围内的唯一整数值。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/increasing-order-search-tree/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
-
创建二叉树
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
-
1. 迭代法（超出时间限制）
类似问题（中序遍历）LeetCode 94. 二叉树的中序遍历 - 简书
思路：使用栈进行中序遍历
public TreeNode increasingBST(TreeNode root) {
TreeNode dummyNode = new TreeNode(0);
TreeNode p = dummyNode;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
p.right = cur;
p.left = null;
p = cur;
cur = cur.right;
}
return p.right;
}
-
2. 递归法
思路：
- 创建一个虚拟根节点 dummyNode;
- 递归进行中序遍历，先遍历左子树，将当前根节点拼接到 cur.right, 并将当前根节点的左子树置空，在遍历右子树
private TreeNode cur;
public TreeNode increasingBST(TreeNode root) {
TreeNode dummyNode = new TreeNode(0);
cur = dummyNode;
helper(root);
return dummyNode.right;
}
private void helper(TreeNode node) {
if (node == null) return;
helper(node.left);
node.left = null;
cur.right = node;
cur = node;
helper(node.right);
}
复杂度分析：
- 时间复杂度：O(n), 需要遍历每个节点
- 空间复杂度：O(n), 由于使用了递归，空间复杂度为O(n)
-
源码
-
我会每天更新新的算法，并尽可能尝试不同解法，如果发现问题请指正
- Github
