AlgorithmClassfication3

144. 二叉树的前序遍历

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
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
Deque<TreeNode> stack = new ArrayDeque<>();
List<Integer> ans = new ArrayList<>();

if (root == null) {
return ans;
}

stack.offerLast(root);
while (!stack.isEmpty()) {
TreeNode tempNode = stack.pollLast();
ans.add(tempNode.val);

if (tempNode.right != null) {
stack.offerLast(tempNode.right);
}
if (tempNode.left != null) {
stack.offerLast(tempNode.left);
}
}

return ans;
}
}

94. 二叉树的中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
Deque<TreeNode> stack = new ArrayDeque<>();
List<Integer> ans = new ArrayList<>();

if (root == null) {
return ans;
}

while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.offerLast(root);
root = root.left;
}

root = stack.pollLast();
ans.add(root.val);
root = root.right;
}

return ans;
}
}

145. 二叉树的后序遍历

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
// 方案一,与中序遍历类似
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root == null) {
return res;
}

Deque<TreeNode> stack = new LinkedList<TreeNode>();
TreeNode prev = null;
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if (root.right == null || root.right == prev) {
res.add(root.val);
prev = root;
root = null;
} else {
stack.push(root);
root = root.right;
}
}
return res;
}
}

// 方法二,与前序遍历类似

230. 二叉搜索树中第K小的元素

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
class Solution {
int num = 0, ans = 0;
public int kthSmallest(TreeNode root, int k) {
searchK(root, k);

return ans;
}

public void searchK(TreeNode node, int k) {
if (node == null) { return; }

searchK(node.left, k);
if (++num == k) {
ans = node.val;
return;
}
searchK(node.right, k);
}
}

// 迭代
class Solution {
/**
* 使用栈进行迭代中序遍历,这样就没有递归中序遍历的全局变量了
* @param root
* @param k
* @return
*/
public int kthSmallest(TreeNode root, int k) {
Deque<TreeNode> stack = new ArrayDeque<>();

// 注意此处没有先加入节点这个操作,而是每次不断的把做节点加入
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.offerLast(root);
root = root.left;
}

root = stack.pollLast();
if (--k == 0) {
return root.val;
}
root = root.right;
}

return root.val;
}
}

240. 搜索二维矩阵 II

297. 二叉树的序列化与反序列化

437. 路径总和 III

路径 不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。

注意:从该节点往下的路径和

所以此处的参数还是写在里面的,而不是返回值里面

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
class Solution {
int ans = 0;
public int pathSum(TreeNode root, int targetSum) {

dfs1(root, targetSum);

return ans;
}

// 遍历所有的节点
public void dfs1(TreeNode node, int targetSum) {

if (node == null) {
return;
}

dfs2(node, targetSum, 0);
dfs1(node.left, targetSum);
dfs1(node.right, targetSum);
}

// 以该节点为跟节点的所有路径和
public void dfs2(TreeNode node, int targetSum, int val) {

if (node == null) {
return;
}

val += node.val;
if (val == targetSum) {
ans += 1;
}
dfs2(node.left, targetSum, val);
dfs2(node.right, targetSum, val);
}
}

450. 删除二叉搜索树中的节点

这道题目的做好好好注意一下,

比如拿到a的left指针node,如果给这个指针赋成别的地址,那么之前的a的left指针是没有变的,因为指向的是固定的地址(除非更改a的left值),而不是指针的指针。

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
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
// 注意,是二叉搜索树呀
// 首先找到,要被删除的节点
TreeNode node = root, nodePar = null;

while (node != null) {
if (key < node.val) {
nodePar = node;
node = node.left;
} else if (key > node.val) {
nodePar = node;
node = node.right;
} else {
break;
}
}

if (null == node) {
return root;
}

// 然后分类删除
if (node.left == null && node.right == null) {
node = null;
} else if (node.left == null) {
node = node.right;
} else if (node.right == null) {
node = node.left;
} else {
// 找出右边节点的最小节点,用它代替到该节点,然后删除
TreeNode succ = node.right, succPar = node;
while (succ.left != null) {
succPar = succ;
succ = succ.left;
}

// 然后将找到的后记节点succ放到node的位置,下面这个判断是succ就是node.right
if (node.right != succ) {
succPar.left = succ.right;
succ.left = node.left;
succ.right = node.right;
} else {
// 如果succ就是node.right,node没有左边节点,直接这样就行
succ.left = node.left;
}
node = succ;
}

if (nodePar == null) { // 被删除的是父节点
return node;
} else if (nodePar.left != null && nodePar.left.val == key) {
nodePar.left = node;
} else {
nodePar.right = node;
}

return root;
}
}

563. 二叉树的坡度

注意:前缀和,高度;从叶子到该节点和

求前缀和,高度等,是从上往下面求的,所以参数放在函数中即可。

但是求从底部叶子到顶部的和,需要将值放在返回值中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
int ans = 0;

public int findTilt(TreeNode root) {
dfs(root);

return ans;
}

public int dfs(TreeNode node) {
if (node == null) {
return 0;
}

int sumLeft = dfs(node.left);
int sumRight = dfs(node.right);

ans += Math.abs(sumRight - sumLeft);
return node.val + sumLeft + sumRight;
}
}

124. 二叉树中的最大路径和

这个也是从低向上,所以可以放在外面

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
class Solution {
int maxSum = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
maxGain(root);
return maxSum;
}

public int maxGain(TreeNode node) {
if (node == null) {
return 0;
}

// 递归计算左右子节点的最大贡献值
// 只有在最大贡献值大于 0 时,才会选取对应子节点
int leftGain = Math.max(maxGain(node.left), 0);
int rightGain = Math.max(maxGain(node.right), 0);

// 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
int priceNewpath = node.val + leftGain + rightGain;

// 更新答案
maxSum = Math.max(maxSum, priceNewpath);

// 返回节点的最大贡献值
return node.val + Math.max(leftGain, rightGain);
}
}

606. 根据二叉树创建字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public String tree2str(TreeNode root) {
return dfs(root);
}

public String dfs(TreeNode node) {
if (node == null) {
return "";
}

if (node.left == null && node.right == null) {
return "" + node.val;
}
if (node.right == null) {
return node.val + "(" + dfs(node.left) + ")";
}
return node.val + "(" + dfs(node.left) + ")(" + dfs(node.right) + ")";
}
}

653. 两数之和 IV - 输入 BST

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
Set<Integer> set = new HashSet<Integer>();

public boolean findTarget(TreeNode root, int k) {
return dfs(root, k);
}

public boolean dfs(TreeNode node, int k) {
if (node == null) {
return false;
}

if (set.contains(k - node.val)) {
return true;
}

set.add(node.val);
return dfs(node.left, k) || dfs(node.right, k);
}
}

783. 二叉搜索树节点最小距离

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
class Solution {
// 二叉搜索树,中序遍历的同时,检查一遍就好
TreeNode pre = null;
int ans = Integer.MAX_VALUE;
public int minDiffInBST(TreeNode root) {
dfs(root);

return ans;
}

public void dfs(TreeNode node) {
if (node == null) {
return;
}

dfs(node.left);

if (pre == null) {
pre = node;
} else {
ans = Math.min(Math.abs(node.val - pre.val), ans);
pre = node;
}

dfs(node.right);
}
}

938. 二叉搜索树的范围和

965. 单值二叉树

993. 二叉树的堂兄弟节点

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
class Solution {
int xDepth = -2;
int yDepth = -1;
TreeNode par = null;
int x, y;
boolean ans = false;

public boolean isCousins(TreeNode root, int x, int y) {
if (root.val == x || root.val == y) {
return false;
}
this.x = x; this.y = y;

dfs(root, 1, null);

return ans;
}

public void dfs(TreeNode node, int height, TreeNode parent) {
if (node == null) {
return;
}

if (node.val == x) {
xDepth = height;
if (par == null) {
par = parent;
} else {
if (xDepth == yDepth && par != parent) {
ans = true;
}
}
} else if (node.val == y) {
yDepth = height;
if (par == null) {
par = parent;
} else {
if (xDepth == yDepth && par != parent) {
ans = true;
}
}
}

dfs(node.left, height+1, node);
dfs(node.right, height+1, node);
}
}

原地哈希

442. 数组中重复的数据

看数组中数据的范围,1 <= nums[i] <= n,而且时间复杂度O(n),空间复杂度常量级别,所以肯定要用到原地哈希。

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
class Solution {
/**
原地哈希
然后numx[i]放到nums[i]-1的位置
*/
public List<Integer> findDuplicates(int[] nums) {
List<Integer> ans = new ArrayList<>();

// 注意,需要两遍,第一遍换到
for (int i=0; i<nums.length; i++) {
// 这是代表已经放在该放的地方了
if (nums[i] < 0 || nums[i]-1 == i) { continue; }
if (nums[nums[i]-1] == nums[i]) {
ans.add(nums[i]);
nums[i] = -1 * nums[i]; // 为了防止重复计算
} else {
int temp = nums[nums[i]-1];
nums[nums[i]-1] = nums[i];
nums[i] = temp;
i--; // 注意这里要i--,因为nums[nums[i]-1]放了现在的nums[i],但是被换过来的这个没有验证
}
}

return ans;
}
}


// 方法2
class Solution {
public List<Integer> findDuplicates(int[] nums) {
int n = nums.length;
List<Integer> ans = new ArrayList<Integer>();
for (int i = 0; i < n; ++i) {
int x = Math.abs(nums[i]);
if (nums[x - 1] > 0) {
nums[x - 1] = -nums[x - 1];
} else {
ans.add(x);
}
}
return ans;
}
}

优先队列、单调队列、treeset、treemap

找到题眼,有任意两个元素之间的绝对差,那肯定是最大值,最小值。

优先队列,跟只用一个变量来维护最大最小值的区别就是:如果删除这个最大的,还能知道下一个最大的,而变量维护的不行了,只能添加得来。

treesetpriorityqueue

1675. 数组的最小偏移量

此处其实用treeset更快。

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
class Solution {
public int minimumDeviation(int[] nums) {
// 使用优先队列,或者使用treeset
// treeset的话可以拿到最大值和最小值
// 而优先队列的话只能拿到一个,此处用最大堆,然后维护最小值
// 先把技术全部*2变成偶数,放入最大堆,然后每次将最大值/2放入,若最大值是奇数,终止

// 最大堆
PriorityQueue<Integer> queue = new PriorityQueue<Integer>((a, b) -> b - a);

int ans = Integer.MAX_VALUE, min = Integer.MAX_VALUE;

for (int num: nums) {
int temp = num % 2 == 1 ? num * 2 : num;
queue.offer(temp);
min = Math.min(temp, min);
}

while (true) {
int max = queue.poll();
ans = Math.min(ans, max - min);

if (max % 2 == 1) { break; } // 若最大值是奇数,终止

int temp = max / 2;
min = Math.min(temp, min);
queue.offer(temp);
}

return ans;
}
}

1438. 绝对差不超过限制的最长连续子数组

还是treemap好用啊,单调队列稍微有点麻烦

注意,这个set不能重复,那么可以用map的值来记录个数,这个思想要记住。

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
class Solution {
public int longestSubarray(int[] nums, int limit) {
// 子数组的任意两个元素之间的绝对值差小于等于limitlimit,经典滑动窗口
// 如何维护最大值和最小值,用treeset吧,但是treeset不能重复啊
// 那可以用treemap啊,值就放他的个数,如果个数为0,需要remove
// 用单调队列维护起来稍微麻烦一点,感觉还是treemap好

TreeMap<Integer, Integer> treeMap = new TreeMap<>();
int left = 0, ans = 0;

for (int right = 0; right < nums.length; right++) {
treeMap.put(nums[right], treeMap.getOrDefault(nums[right], 0) + 1);

while (left < right && treeMap.lastKey() - treeMap.firstKey() > limit) {
treeMap.put(nums[left], treeMap.get(nums[left]) - 1);
if (treeMap.get(nums[left]) == 0) {
treeMap.remove(nums[left]);
}
left += 1;
}

ans = Math.max(ans, right - left + 1);
}

return ans;
}
}

Author: Jcwang

Permalink: http://example.com/2022/07/13/AlgorithmClassfication3/