0%

leetcode 538、1038

力扣538和1038,从二叉搜索树到更大的树

皮卡丘

首先说明这两个题是一样的,就是把一个二叉搜索树的每个节点的值变成它与所有比它大的值的和。

递归反中序遍历

首先第一种方法就是递归,因为对于树来说,递归是最简单的方法了

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
/*
* @lc app=leetcode.cn id=538 lang=java
*
* [538] 把二叉搜索树转换为累加树
*/

// @lc code=start
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {

int sum = 0;//用来保存每个节点最后相加的值,每次更新

public TreeNode convertBST(TreeNode root) {
if(root == null){
return null;
}else{
//二叉搜索树,左小右大
convertBST(root.right);
sum += root.val;
root.val = sum;
convertBST(root.left);
}
return root;
}
}
// @lc code=end

Morris 遍历

还有一种方法就是Morris 遍历,可以把空间复杂度从O(n)降到O(1)

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/*
* @lc app=leetcode.cn id=1038 lang=java
*
* [1038] 从二叉搜索树到更大和树
*/

// @lc code=start
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
/**
* 解题思路:反中序遍历
* 1:如果当前节点的右节点为空,则处理当前节点,然后遍历当前节点到左子树
* 2:如果当前节点的右节点不为空,则找到右子树最左节点succ
* 1:若succ的左子树为空,则令其指向当前节点,然后node = node.right
* 2:若succ的左子树不为空,则置空(恢复原树),然后node = node.left
*
*/
class Solution {
public TreeNode bstToGst(TreeNode root) {
int sum = 0;
TreeNode node = root;

while(node != null){
if(node.right == null){
sum += node.val;
node.val = sum;
node = node.left;
}else if(node != null){
TreeNode succ = getSuccessor(node);
if(succ.left == null){
succ.left = node;
node = node.right;
}else if(succ.left != null){
succ.left = null;
sum += node.val;
node.val = sum;
node = node.left;
}
}
}
return root;
}

//找到当前节点右子树到最左节点
public TreeNode getSuccessor(TreeNode node){
TreeNode succ = node.right;
while(succ.left != null && succ.left != node){
succ = succ.left;
}
return succ;
}
}
// @lc code=end
-------------本文结束感谢您的阅读-------------