LeetCode-Tree

Free Talk

终于可以刷最常用的二叉树了,我对于二叉树的递归和迭代理解的不是很清楚,趁这篇文章学习总结一下。

Finished Problem

image-20201105095907511

验证二叉搜索树

98. 验证二叉搜索树

递归

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
// 二叉搜索树的特征记一下
// 可以采用 DFS 深度优先遍历
// 这边给定范围的做法特别妙
return dfs(root, null, null);
}

public boolean dfs(TreeNode root, Integer low, Integer high){
// 先给定终止条件
if(root == null) return true;

if(low != null && root.val <= low){
return false;
}
if(high != null && root.val >= high){
return false;
}

if(!dfs(root.left, low, root.val)) return false;
if(!dfs(root.right, root.val, high)) return false;

return true;
}
}

执行结果

image-20201105110103479

中序遍历

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
long pre = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
// 采用中序遍历
// 因为中序遍历是先访问左子树,再访问节点,然后访问右子树
// 因此二叉搜索树中序遍历的结果,应该是递增的
if(root == null) return true;

if(!isValidBST(root.left)){
return false;
}

if(root.val <= pre){
return false;
}

pre = root.val;

if(!isValidBST(root.right)){
return false;
}

return true;
}
}

执行结果

image-20201105111103403

从前序与中序遍历序列构造二叉树

105. 从前序与中序遍历序列构造二叉树

递归 (根节点 + 左右子树)

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
// 这种题好像以前在数据结构课程中做过
// 前序遍历:根 左 右
// 中序遍历:左 根 右
// 看了题解,发现和我当初解题的思路是一样的,不过考试的时候没考算法
// 我们可以观察到可以从前序遍历直接得到根节点
// 再根据根节点,从中序遍历得到左右子树
// 不停地递归左右子树
return buildTreeHelper(preorder, 0, preorder.length, inorder, 0 , inorder.length);

}

public TreeNode buildTreeHelper(int[] preorder, int pStart, int pEnd,
int []inorder, int iStart, int iEnd){
// 相等意味着已经遍历完前序数组,直接返回
if(pStart == pEnd){
return null;
}

int root_val = preorder[pStart];
TreeNode root = new TreeNode(root_val);

int root_index = 0;
for(int i = iStart; i < iEnd; i ++ ){
if(inorder[i] == root_val){
root_index = i;
break;
}
}

int left = root_index - iStart;

// 这边的数组的起始位置需要注意一下
root.left = buildTreeHelper(preorder, pStart + 1, pStart + left + 1, inorder,iStart, root_index);
root.right = buildTreeHelper(preorder,pStart + left + 1, pEnd, inorder, root_index + 1, iEnd);

return root;
}
}

执行结果

image-20201105141747473

哈希表优化

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
// 再刚刚的题解上做一个优化
// 查找根节点的索引位置,由循环遍历改为哈希表存放
HashMap<Integer,Integer> map = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
// 这种题好像以前在数据结构课程中做过
// 前序遍历:根 左 右
// 中序遍历:左 根 右
// 看了题解,发现和我当初解题的思路是一样的,不过考试的时候没考算法
// 我们可以观察到可以从前序遍历直接得到根节点
// 再根据根节点,从中序遍历得到左右子树
// 不停地递归左右子树
for(int i = 0; i < inorder.length; i ++ ){
map.put(inorder[i],i);
}
return buildTreeHelper(preorder, 0, preorder.length, inorder, 0 , inorder.length);

}

public TreeNode buildTreeHelper(int[] preorder, int pStart, int pEnd,
int []inorder, int iStart, int iEnd){
// 相等意味着已经遍历完前序数组,直接返回
if(pStart == pEnd){
return null;
}

int root_val = preorder[pStart];
TreeNode root = new TreeNode(root_val);

int root_index = 0;
root_index = map.get(root_val);

int left = root_index - iStart;

// 这边的数组的起始位置需要注意一下
root.left = buildTreeHelper(preorder, pStart + 1, pStart + left + 1, inorder,iStart, root_index);
root.right = buildTreeHelper(preorder,pStart + left + 1, pEnd, inorder, root_index + 1, iEnd);

return root;
}
}

执行结果

image-20201105142210925

二叉树展开为链表

114. 二叉树展开为链表

前序遍历

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public void flatten(TreeNode root) {
// 看起来很简单
// 展开顺序:根 左 右
// 那这个就是前序遍历
// 返回结果是 void, 那应该是在二叉树上直接做修改
while(root != null){
if(root.left == null){
// 左子树为空,将根节点置为右子树
root = root.right;
}else{
// 将右子树接到左子树的最右节点上
TreeNode pre = root.left;
while(pre.right != null){
pre = pre.right;
}

pre.right = root.right;
// 将左子树接到右子树的节点
root.right = root.left;
// 左子树设置为空
root.left = null;

root = root.right;
}
}
}
}

执行结果

image-20201105165801114

二叉树中的最大路径和

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

根据字符出现频率排序

451. 根据字符出现频率排序

桶排序

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
class Solution {
public String frequencySort(String s) {
// 看到跟谁学的面经里面有这道题
// 利用桶排序做法

// 初始化 HashMap
HashMap<Character,Integer> map = new HashMap<>();
char[] array = s.toCharArray();
for(char ch: array){
map.put(ch,map.getOrDefault(ch, 0) + 1 );
}

// 装桶
List<Character>[] list = new List[s.length() + 1];
// 遍历 key,将 value相同的字母加入同一个链表
for(char key: map.keySet()){
int i = map.get(key);
if(list[i] == null ){
list[i] = new ArrayList<>();
}
list[i].add(key);
}

// 倒桶,按照字母出现次数的高低,倒序输出
char[] res = new char[s.length()];
int index = 0;
for(int i = s.length(); i > 0; i --){
if(list[i] == null) continue;
for(char ch: list[i]){
for(int j = 0; j < i ; j ++ ){
res[index ++ ] = ch;
}
}
}

return new String(res);
}
}

执行结果

image-20201106001122725

二叉树的右视图

199. 二叉树的右视图

层序遍历 + 队列 + 输出最后一个元素

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> rightSideView(TreeNode root) {
// 今天面试的时候就考了这一题,结果我没想出来层序遍历怎么写
// 层序遍历需要使用队列来 存放
// 以后每天晚上睡觉前,都把刷过的题目再看一遍

List<Integer> list = new ArrayList<>();
// 一般使用 链表来实现队列
Queue<TreeNode> queue = new LinkedList<>();

if(root != null){
queue.offer(root);
}

while(!queue.isEmpty()){
int size = queue.size();
for(int i = 0; i < size ; i ++ ){
TreeNode pre = queue.poll();
if(i == size - 1){
list.add(pre.val);
}
if(pre.left != null){
queue.offer(pre.left);
}
if(pre.right != null){
queue.offer(pre.right);
}
}
}

return list;
}
}

执行结果

image-20201106205119924

DFS + 深度判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 在面试的过程中,使用的界面就相当于记事本,需要自己去写函数和类
class Solution{
List<Integer> res = new ArrayList<>();

public List<Integer> rightSideView(TreeNode root){
dfs(root, 0);
return res;
}

// 按照 根 右 左 的顺序遍历
public void dfs(TreeNode root, int depth){
if(root == null) return ;

if(depth == res.size()){
res.add(root.val);
}
depth ++;
dfs(root.right,depth);
dfs(root.left,depth);
return ;
}
}

执行结果

image-20201106210807088

二叉树的最近公共祖先

236. 二叉树的最近公共祖先

后序遍历

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 递归我总是想不清楚
// 从下往上的找,可以利用 左 右 根 后序遍历

if(root == null || root == p || root == q) return root;

TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p , q);

if(left == null) return right;
if(right == null) return left;

return root;
}

}

执行结果

image-20201107231950835

打家劫舍 III

337. 打家劫舍 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
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int rob(TreeNode root) {
// 像是最优化问题
int max1 = 0;
int max2 = 0;
int depth = 0;
// 好像是可以用层序遍历,他是一层层的盗取
Queue<TreeNode> queue = new LinkedList<>();
if(root != null) {
queue.offer(root);
}

while(!queue.isEmpty()){
int size = queue.size();
depth ++;
for(int i = 0; i < size ; i ++ ){
TreeNode pre = queue.poll();
if(depth % 2 == 1){
max1 += pre.val;
if(pre.left != null){
queue.offer(pre.left);
}
if(pre.right != null){
queue.offer(pre.right);
}
}else{
max2 += pre.val;
if(pre.left != null){
queue.offer(pre.left);
}
if(pre.right != null){
queue.offer(pre.right);
}
}
}
}

return Math.max(max1, max2);
}
}

DFS+哈希表

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
HashMap<TreeNode,Integer> choose = new HashMap<>();
HashMap<TreeNode,Integer> ignore = new HashMap<>();

public int rob(TreeNode root) {
// 采用深度优先搜索,利用哈希表存放节点的状态
// 选择这个节点的最大值,不选择这个节点的最大值
dfs(root);
return Math.max(choose.getOrDefault(root, 0), ignore.getOrDefault(root, 0));
}

public void dfs(TreeNode root){
if(root == null) return ;
dfs(root.left);
dfs(root.right);

choose.put(root, root.val + ignore.getOrDefault(root.left, 0) + ignore.getOrDefault(root.right, 0));
ignore.put(root, Math.max(choose.getOrDefault(root.left, 0), ignore.getOrDefault(root.left, 0)) + Math.max(choose.getOrDefault(root.right, 0), ignore.getOrDefault(root.right, 0)));

return;
}
}

执行结果

image-20201108000213034

路径总和 III

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
37
38
39
40
41
42
43
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
HashMap<Integer, Integer> map = new HashMap<>();
public int pathSum(TreeNode root, int sum) {
// 为什么自己这么垃圾啊,刚刚写的时候也想过用一个HashMap来存放节点的和
// 但是就是考虑不到可以利用两个节点之间的前缀和关系
map.put(0, 1);
return getPath(root, sum, 0);
}

public int getPath(TreeNode root, int sum, int count){
if(root == null) return 0;

int res = 0;
count += root.val;
// 如果一个节点的前缀和为 count , 另一个节点的前缀和为 count - sum,
// 则两个节点之间的前缀和为 sum
res += map.getOrDefault(count - sum, 0);
map.put(count, map.getOrDefault(count, 0) + 1);

res += getPath(root.left, sum, count);
res += getPath(root.right, sum, count);

// 因为只有当前的节点的子节点才会用到该节点的前缀和,因此返回后需要清楚
map.put(count, map.getOrDefault(count, 0) - 1);

return res;
}
}

执行结果

image-20201108155209048

双重递归

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int pathSum(TreeNode root, int sum) {
// 双重递归的思路,是从一个节点开始,去递归它是否存放一条和为sum的路径
// 之后再从别的节点开始重新递归
if(root == null) return 0;

return getPath(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
}

public int getPath(TreeNode root, int sum){
if(root == null) return 0;

int res = (sum - root.val) == 0 ? 1 : 0;

return res + getPath(root.left, sum - root.val) + getPath(root.right, sum - root.val);
}
}

执行结果

image-20201108161450505

把二叉搜索树转换为累加树

538. 把二叉搜索树转换为累加树

DFS + 右根左

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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
int sum = 0;
public TreeNode convertBST(TreeNode root) {
// 右 根 左
dfs(root);
return root;
}

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

dfs(root.right);
root.val += sum;
sum = root.val;
dfs(root.left);

return ;
}
}

执行结果

image-20201108164323770

第一目标完成

image-20201108164543962

自己刷了十几题的树,发现所有的题其实都是遍历问题,要学会把握遍历的顺序(根,左,右 间的次序交换)。

但是自己离十五分钟内,做出中等难度的算法题的目标,还相差甚远。因此打算另开一张,继续接着刷树类型,及其他高频的算法题。