Skip to content

Commit f6c0f1b

Browse files
linwtlinwt
committed
二叉树总结
1 parent f13d189 commit f6c0f1b

24 files changed

+560
-142
lines changed

‎leetcode_Java/DoneTitle.txt

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -138,7 +138,7 @@
138138
407. 接雨水 II
139139
415. 字符串相加
140140
416. 分割等和子集
141-
437. 路径总和
141+
437. 路径总和 III
142142
438. 找到字符串中所有字母异位词
143143
448. 找到所有数组中消失的数字
144144
461. 汉明距离

‎leetcode_Java/DoneType.txt

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -34,7 +34,7 @@
3434
226. 翻转二叉树
3535
236. 二叉树的最近公共祖先
3636
297. 二叉树的序列化与反序列化
37-
437. 路径总和
37+
437. 路径总和 III
3838
538. 把二叉搜索树转换为累加树
3939
543. 二叉树的直径
4040
589. N叉树的前序遍历

‎leetcode_Java/Solution0094.java

Lines changed: 17 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -19,14 +19,23 @@
1919

2020

2121
/*
22-
* 递归思路：
23-
* 1、定义数据结构：使用列表成员变量，存储每次递归操作存入的值
24-
* 2、递归终止条件：节点为空时返回
25-
* 3、单层递归逻辑：把节点的值存入列表
26-
* 4、递归逻辑：
27-
* 左右节点需要与根节点做同样的事，就要调同样的方法，即递归
28-
* 确定递归顺序/遍历顺序，左中右
29-
* 每层不需要接收使用递归方法返回值，列表成员变量存储了结果
22+
递归思路：
23+
1、定义数据结构：使用列表成员变量，存储每次递归操作存入的值
24+
2、递归终止条件：节点为空时返回
25+
3、单层递归逻辑：把节点的值存入列表
26+
4、递归逻辑：
27+
左右节点需要与根节点做同样的事，就要调同样的方法，即递归
28+
确定递归顺序/遍历顺序，左中右
29+
每层不需要接收使用递归方法返回值，列表成员变量存储了结果
30+
=================================================
31+
新模板注释，递归
32+
节点值加入列表递归函数
33+
1、方法功能：入参是一个节点，将该节点值加入列表，返回列表
34+
2、终止条件：节点为空时，返回列表
35+
3、一个节点处理过程和返回结果：将节点值加入列表，返回列表
36+
4、递归调用：左右节点同样需要加入列表，因此调用同样的方法处理
37+
5、递归顺序：中序遍历，先处理左节点，再处理根节点，最后处理右节点
38+
6、使用递归调用结果和返回结果：不用接收递归调用结果，节点已经加入列表了，直接返回列表即可
3039
* */
3140
class Solution {
3241
public List<Integer> list = new ArrayList<>();

‎leetcode_Java/Solution0098.java

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -18,6 +18,26 @@
1818
*/
1919

2020

21+
/*
22+
有效二叉搜索树定义如下：
23+
1、节点的左子树只包含 小于 当前节点的数。
24+
2、节点的右子树只包含 大于 当前节点的数。
25+
3、所有左子树和右子树自身必须也是二叉搜索树。
26+
*/
27+
28+
29+
/*
30+
中序遍历：
31+
1、方法功能：入参是一个节点，判断当前节点是否比前一节点大，不是则返回false，是则返回true
32+
2、终止条件：节点为空时返回true，才能继续遍历不为空的节点
33+
3、单节点处理过程和返回结果：判断当前节点是否比前一节点大，不是则返回false，是则保存当前节点值，并返回true
34+
4、递归调用：左右节点需要同样的操作，因此调用同样的方法处理，获取结果
35+
5、递归顺序：中序遍历，根节点的处理依赖左节点的值，右节点的处理依赖根节点的值。需要中序遍历有序地保存前一节点值，给下一节点判断
36+
6、使用递归调用结果和返回结果：
37+
1）左节点不满足则返回false，满足则继续判断根节点；
38+
2）根节点不满足则返回false，满足则继续判断右节点；
39+
3）右节点不满足则返回false，满足则返回true，即直接返回右节点处理结果即可
40+
*/
2141
class Solution {
2242
private long pre = Long.MIN_VALUE;
2343

@@ -37,6 +57,15 @@ public boolean isValidBST(TreeNode root) {
3757
}
3858

3959

60+
/*
61+
递归：
62+
1、方法功能：入参是节点、最小值、最大值，判断节点值是否有效，即是否满足 min < val < max，有效效返回true，无效返回false
63+
2、终止条件：节点为空返回true
64+
3、单节点处理过程和返回结果：判断节点值是否有效，即是否满足 min < val < max，有效效返回true，无效返回false
65+
4、递归调用：左右节点需要同样的操作，因此调用同样的方法处理，获取结果
66+
5、递归顺序：前序遍历，左右节点的处理依赖根节点的值，所以要先处理根节点，再处理左右节点
67+
6、使用递归调用结果和返回结果：左右节点同时有效则返回true，否则返回false
68+
*/
4069
class Solution {
4170
public boolean isValidBST(TreeNode root) {
4271
return isValid(root, null, null);

‎leetcode_Java/Solution0101.java

Lines changed: 25 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -19,18 +19,31 @@
1919

2020

2121
/*
22-
* 递归思路：
23-
* 1、方法定义：
24-
* 1）由于要判断两个节点对应的左右子节点值是否相同，原方法入参只有一个节点不够用，需要再定义一个有两个节点作为入参的方法
25-
* 2）不管是原方法还是新方法，其返回类型和返回结果都跟题目要求的返回类型和返回结果一致
26-
* 2、方法功能：
27-
* 1）入参是两个节点，判断两个节点是否相同
28-
* 2）节点都为空、节点都不为空且值相等则返回true；节点只有一个不为空、节点都不为空但值不相等则返回false
29-
* 3、递归逻辑：
30-
* 1）两个节点的左右子节点同样可以调用这个方法，判断节点是否相同，得到true或false的结果
31-
* 2）当前层节点对称，才会继续递归下一层
32-
* 3）每一层，每两个节点作为入参，调用方法，都得到了true或false的结果
33-
* 4）上一层使用下一层的结果，将下一层多个结果进行与运算，得到下一层的节点是否对称
22+
递归思路：
23+
1、方法定义：
24+
1）由于要判断两个节点对应的左右子节点值是否相同，原方法入参只有一个节点不够用，需要再定义一个有两个节点作为入参的方法
25+
2）不管是原方法还是新方法，其返回类型和返回结果都跟题目要求的返回类型和返回结果一致
26+
2、方法功能：
27+
1）入参是两个节点，判断两个节点是否相同
28+
2）节点都为空、节点都不为空且值相等则返回true；节点只有一个不为空、节点都不为空但值不相等则返回false
29+
3、递归逻辑：
30+
1）两个节点的左右子节点同样可以调用这个方法，判断节点是否相同，得到true或false的结果
31+
2）当前层节点对称，才会继续递归下一层
32+
3）每一层，每两个节点作为入参，调用方法，都得到了true或false的结果
33+
4）上一层使用下一层的结果，将下一层多个结果进行与运算，得到下一层的节点是否对称
34+
=======================================================================================================
35+
新注释模板，递归
36+
1、方法功能：判断对称需要两个节点参与，入参是两个节点，判断两个节点值是否相同，相同返回true，不同返回false
37+
2、终止条件：两个节点都为空时，返回true
38+
3、两个节点处理过程和返回结果：判断两个节点值是否相同，相同返回true，不同返回false
39+
4、递归调用：两个节点对应的两对左右节点值同样需要判断是否相同，因此调用同样的方法处理，获取结果
40+
5、递归顺序：前序遍历，先判断当前两个节点值是否相同，不同则结束返回false，相同则继续判断两对左右节点值是否相同
41+
6、使用递归调用结果和返回结果：两对左右节点值都相同则返回true，否则返回false
42+
1
43+
/ \
44+
2 2
45+
/ \ / \
46+
3 4 4 3
3447
* */
3548
class Solution {
3649
public boolean isSymmetric(TreeNode root) {

‎leetcode_Java/Solution0102.java

Lines changed: 48 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -99,33 +99,64 @@ public List<List<Integer>> levelOrder(TreeNode root) {
9999

100100

101101
/*
102-
* 递归思路：
103-
* 1、定义数据结构：成员变量：列表存放递归结果
104-
* 局部变量：子列表存放每层节点值
105-
* 2、辅助标记：整型变量标记 层的深度 对应 子列表的索引
106-
* 3、递归逻辑：
107-
* 1）前序遍历，深度优先搜索，每个节点都会遍历到，每层节点最终都是从左到右按序访问
108-
* 2）记录节点所在层的深度，每到新的一层就创建一个新的子列表，层的深度对应子列表的索引，节点值层序存放
102+
递归思路：
103+
1、定义数据结构：成员变量：列表存放递归结果
104+
局部变量：子列表存放每层节点值
105+
2、辅助标记：整型变量标记 层的深度 对应 子列表的索引
106+
3、递归逻辑：
107+
1）前序遍历，深度优先搜索，每个节点都会遍历到，每层节点最终都是从左到右按序访问
108+
2）记录节点所在层的深度，每到新的一层就创建一个新的子列表，层的深度对应子列表的索引，节点值层序存放
109+
========================================================================================
110+
新注释模板，递归
111+
1、方法功能：入参是节点、层数，将节点值加入该层的子列表中。层数参数逐层累加，标记当前所在层，方便对应获取当前层的子列表
112+
2、终止条件：节点为空时，结束
113+
3、一个节点处理过程和返回结果：当该层的子列表未创建时，则创建子列表加入全局列表中。将节点值加入该层的子列表中
114+
4、递归调用：左右节点同样需要加入对应层的子列表中，因此调用同样的方法处理
115+
5、递归顺序：前序遍历，要求层序遍历，所以要先处理根节点，再处理左右节点
116+
6、使用递归调用结果和返回结果：不用接收返回结构，将节点值加入子列表即可
109117
* */
110118
class Solution {
111-
public List<List<Integer>> list = new ArrayList<>();
119+
List<List<Integer>> list = new ArrayList<>();
112120

113121
public List<List<Integer>> levelOrder(TreeNode root) {
114-
return dfs(root, 0);
122+
dfs(root, 1);
123+
return list;
115124
}
116125

117-
public List<List<Integer>> dfs(TreeNode root, int deep) {
126+
public void dfs(TreeNode root, int layer) {
127+
if (root == null) {
128+
return;
129+
}
130+
if (list.size() < layer) {
131+
list.add(new ArrayList<>());
132+
}
133+
list.get(layer - 1).add(root.val);
134+
dfs(root.left, layer + 1);
135+
dfs(root.right, layer + 1);
136+
}
137+
}
138+
139+
140+
/*
141+
上一解法递归函数返回类型为void，但也可以顺便利用返回结果，不接收处理，目的是最后把结果列表返回了
142+
*/
143+
class Solution {
144+
List<List<Integer>> list = new ArrayList<>();
145+
146+
public List<List<Integer>> levelOrder(TreeNode root) {
147+
return dfs(root, 1);
148+
}
149+
150+
public void dfs(TreeNode root, int layer) {
118151
if (root == null) {
119152
return list;
120153
}
121-
deep++;
122-
if (list.size() < deep) {
123-
List<Integer> sonList = new ArrayList<>();
124-
list.add(sonList);
154+
if (list.size() < layer) {
155+
list.add(new ArrayList<>());
125156
}
126-
list.get(deep - 1).add(root.val);
127-
dfs(root.left, deep);
128-
dfs(root.right, deep);
157+
list.get(layer - 1).add(root.val);
158+
dfs(root.left, layer + 1);
159+
dfs(root.right, layer + 1);
129160
return list;
130161
}
131162
}

‎leetcode_Java/Solution0104.java

Lines changed: 14 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -19,12 +19,20 @@
1919

2020

2121
/*
22-
* 递归思路：
23-
* 1、方法功能：入参是一个节点，节点为空返回0，节点不为空返回1
24-
* 2、递归逻辑：
25-
* 1）左右节点同样可以调用这个方法，得到0或1的结果
26-
* 2）每一层，每个节点，调用方法，都得到了0或1的结果
27-
* 3）上一层使用下一层的结果，取下一层左右节点结果的最大值，累加到当前层，从而得到二叉树的最大深度
22+
递归思路：
23+
1、方法功能：入参是一个节点，节点为空返回0，节点不为空返回1
24+
2、递归逻辑：
25+
1）左右节点同样可以调用这个方法，得到0或1的结果
26+
2）每一层，每个节点，调用方法，都得到了0或1的结果
27+
3）上一层使用下一层的结果，取下一层左右节点结果的最大值，累加到当前层，从而得到二叉树的最大深度
28+
==================================================================================
29+
计算深度递归函数
30+
1、方法功能：入参是一个节点，返回节点的深度
31+
2、终止条件：节点为空时返回0
32+
3、一个节点处理过程和返回结果：节点不为空时返回1
33+
4、递归调用：左右节点同样需要计算深度，因此调用同样的方法处理，获取结果
34+
5、递归顺序：后序遍历，当前节点的深度计算依赖左右节点的深度
35+
6、使用递归调用结果和返回结果：当前节点的深度 = 1 + max(左节点深度, 右节点深度)
2836
* */
2937
class Solution {
3038
public int maxDepth(TreeNode root) {

‎leetcode_Java/Solution0105.java

Lines changed: 45 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -18,13 +18,21 @@
1818
*/
1919

2020

21-
/**
22-
* 递归思路：
23-
* 1、方法功能：入参是两个数组，两个数组都为空时返回空，不为空时创建、返回根节点
24-
* 2、递归逻辑：
25-
* 1）根据前、中序数组的特点，拆分出左子树和右子树两部分数组
26-
* 2）左右子树的数组同样可以调用这个方法，得到左右子树的根节点
27-
* 3）上一层使用下一层的结果，取下一层左子树的根节点作为当前层的左子节点，取下一层右子树的根节点作为当前层的右子节点
21+
/*
22+
递归思路：
23+
1、方法功能：入参是两个数组，两个数组都为空时返回空，不为空时创建、返回根节点
24+
2、递归逻辑：
25+
1）根据前、中序数组的特点，拆分出左子树和右子树两部分数组
26+
2）左右子树的数组同样可以调用这个方法，得到左右子树的根节点
27+
3）上一层使用下一层的结果，取下一层左子树的根节点作为当前层的左子节点，取下一层右子树的根节点作为当前层的右子节点
28+
===============================================================================================
29+
构造节点递归函数
30+
1、方法功能：入参是前序、中序数组，构造根节点，并返回根节点
31+
2、终止条件：两个数组都为空时，返回空
32+
3、一个节点处理过程和返回结果：获取前序数组首元素，构造根节点，返回根节点
33+
4、递归调用：左右节点同样需要构造，因此调用同样的方法递归处理，获取结果
34+
5、递归顺序：前序遍历，要先构造根节点，再去构造左右节点
35+
6、使用递归调用结果和返回结果：获取左右节点后，将其与根节点连接，然后返回根节点
2836
*/
2937
class Solution {
3038
public TreeNode buildTree(int[] preorder, int[] inorder) {
@@ -40,36 +48,46 @@ public TreeNode buildTree(int[] preorder, int[] inorder) {
4048
}
4149

4250

43-
/**
44-
* 递归思路：
45-
* 1、数据结构：
46-
* 1）使用Map存放中序数组的元素和索引，方便直接获取索引，避免了重复遍历获取
47-
* 2）使用指针表示数组的开始和结束位置，避免了数组的拆分和拷贝，节省额外空间。注意两个指针指向的数组范围是包括左边界，不包括右边界
48-
* 2、递归逻辑：
49-
* 1）原方法入参不够用，创建一个新的方法作为递归方法
50-
* 2）方法的功能：终止条件，当数组为空时，前序起始、结束指针位置相同，返回空；不为空时创建、返回根节点
51-
* 3）通过指针划分左右子树的数组范围，调用同个方法得到左右子树的根节点
52-
* 4）上一层使用下一层的结果，取下一层左子树的根节点作为当前层的左子节点，取下一层右子树的根节点作为当前层的右子节点
51+
/*
52+
递归思路：
53+
1、数据结构：
54+
1）使用Map存放中序数组的元素和索引，方便直接获取索引，避免了重复遍历获取
55+
2）使用指针表示数组的开始和结束位置，避免了数组的拆分和拷贝，节省额外空间。注意两个指针指向的数组范围是包括左边界，不包括右边界
56+
2、递归逻辑：
57+
1）原方法入参不够用，创建一个新的方法作为递归方法
58+
2）方法的功能：终止条件，当数组为空时，前序起始、结束指针位置相同，返回空；不为空时创建、返回根节点
59+
3）通过指针划分左右子树的数组范围，调用同个方法得到左右子树的根节点
60+
4）上一层使用下一层的结果，取下一层左子树的根节点作为当前层的左子节点，取下一层右子树的根节点作为当前层的右子节点
61+
============================================================================================================
62+
新注释模板，递归
63+
构造节点递归函数
64+
1、方法功能：入参是两个数组、对应的开始和结束边界
65+
2、终止条件：开始边界等于结束边界，说明数组为空，返回空
66+
3、一个节点处理过程和返回结果：获取前序数组首元素，构造根节点，返回根节点
67+
4、递归调用：左右节点同样需要构造，因此调用同样的方法递归处理，获取结果
68+
5、递归顺序：前序遍历，要先构造根节点，再去构造左右节点
69+
6、使用递归调用结果和返回结果：获取左右节点后，将其与根节点连接，然后返回根节点
5370
*/
5471
class Solution {
72+
Map<Integer, Integer> map = new HashMap<>();
73+
5574
public TreeNode buildTree(int[] preorder, int[] inorder) {
56-
Map<Integer, Integer> map = new HashMap<>();
5775
for (int i = 0; i < inorder.length; i++) {
5876
map.put(inorder[i], i);
5977
}
60-
return buildTreeHelper(preorder, 0, preorder.length, inorder, 0, inorder.length, map);
78+
return buildTreeHelper(preorder, 0, preorder.length, inorder, 0, inorder.length);
6179
}
6280

63-
public TreeNode buildTreeHelper(int[] preorder, int p_start, int p_end, int[] inorder, int i_start, int i_end, Map<Integer, Integer> map) {
64-
if (p_start == p_end) {
81+
public TreeNode buildTreeHelper(int[] preorder, int pStart, int pEnd, int[] inorder, int iStart, int iEnd) {
82+
if (pStart == pEnd) {
6583
return null;
6684
}
67-
int root_val = preorder[p_start];
68-
TreeNode root = new TreeNode(root_val);
69-
int i_root_index = map.get(root_val);
70-
int left_num = i_root_index - i_start;
71-
root.left = buildTreeHelper(preorder, p_start + 1, p_start + left_num + 1, inorder, i_start, i_root_index, map);
72-
root.right = buildTreeHelper(preorder, p_start + left_num + 1, p_end, inorder, i_root_index + 1, i_end, map);
85+
int rootVal = preorder[pStart];
86+
TreeNode root = new TreeNode(rootVal);
87+
int iRootIndex = map.get(rootVal);
88+
int leftNum = iRootIndex - iStart;
89+
root.left = buildTreeHelper(preorder, pStart + 1, pStart + leftNum + 1, inorder, iStart, iRootIndex);
90+
root.right = buildTreeHelper(preorder, pStart + leftNum + 1, pEnd, inorder, iRootIndex + 1, iEnd);
7391
return root;
7492
}
7593
}

0 commit comments

Comments
 (0)