把树变成队列,再排序,前i个值求和,在根据节点的值进行二分查找,这个是理想算法,
实际是,复杂度没那么高,直接把树变成队列,for循环解决战斗
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
31
32
33
34
35
36
37
38
39
40
41
|
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode bstToGst(TreeNode root) {
ArrayList<Integer> list = new ArrayList<Integer>();
dfs(root,list);
dfs2(root,list);
return root;
}
public void dfs(TreeNode root,ArrayList<Integer> list) {
if(root==null){
return ;
}
list.add(root.val);
dfs(root.left,list);
dfs(root.right,list);
}
public void dfs2(TreeNode root,ArrayList<Integer> list){
if(root==null){
return;
}
int sum = 0;
for(Integer value : list){
if (value>=root.val){
sum = sum+value;
}
}
root.val = sum;
dfs2(root.left,list);
dfs2(root.right,list);
}
}
|
近期评论