LeetCode 897 Increasing Order Search Tree

题意

给定一颗二叉搜索树,重新进行排序,使其根节点是最小值,且每个节点都没有左子树,只有一个右子树,最终还要保持该树是一颗二叉搜索树.

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
例 1:
给予树:

5
/ \
3 6
/ \ \
2 4 8
/ / \
1 7 9

输出:

1
\
2
\
3
\
4
\
5
\
6
\
7
\
8
\
9

解法

使用中序遍历即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private TreeNode result = new TreeNode(0);
private TreeNode dummy = result;

public TreeNode increasingBST(TreeNode root) {
if (root == null) {
return null;
}
increasingBST(root.left);
dummy.right = new TreeNode(root.val);
dummy = dummy.right;
increasingBST(root.right);
return result.right;
}
}

Runtime: 2 ms, faster than 99.97% of Java online submissions for Increasing Order Search Tree.

Memory Usage: 44.9 MB, less than 59.39% of Java online submissions for Increasing Order Search Tree.

  • 本文作者: 赵俊
  • 本文链接: http://www.zhaojun.im/leetcode-897/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!