Skip to content

Commit 4da688e

Browse files
linwtlinwt
committed
二叉树前中后序遍历，辅助数组解法
1 parent 47b3550 commit 4da688e

3 files changed

Lines changed: 152 additions & 1 deletion

File tree

‎leetcode_Java/Solution0094.java‎

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -133,4 +133,55 @@ public List<Integer> inorderTraversal(TreeNode root) {
133133
}
134134
return list;
135135
}
136+
}
137+
138+
139+
/*
140+
* 迭代思路：
141+
* 1、定义数据结构：结果列表存放排序节点值；节点列表按序存放节点；索引列表存放未判断是否有左右子节点的节点
142+
* 2、数据结构初始化：根节点存入节点列表；索引0存入索引列表
143+
* 3、迭代逻辑：
144+
* 1）索引列表不为空时，说明有节点未判断是否有左右子节点，循环遍历索引列表
145+
* 2）索引列表降序排序，取出最大索引，对该索引的节点进行操作。先处理靠右边的节点，可以防止插入节点时影响了节点列表其他节点的位置
146+
* 3）是否有子节点存在四种情况：有左右节点、只有右节点、只有左节点、没有左右节点。要分别处理，不同情况节点最终索引位置不同
147+
* 4）中序遍历：
148+
* 先插入右节点，再插入左节点
149+
* 插入右节点是在根节点右边插入，其他结点右移一位
150+
* 插入左节点是替代了根节点的位置，根节点和其他结点右移一位
151+
* 5）最大索引的节点判断完左右节点后，移除索引列表的最大索引
152+
* 6）最终节点列表按序排序，遍历结点列表，将节点值存入结果列表
153+
* */
154+
public class Solution0094 {
155+
public List<Integer> inorderTraversal(TreeNode root) {
156+
List<Integer> resList = new ArrayList<>();
157+
if (root == null) {
158+
return resList;
159+
}
160+
List<TreeNode> nodeList = new ArrayList<>();
161+
List<Integer> indexList = new ArrayList<>();
162+
nodeList.add(root);
163+
indexList.add(0);
164+
while (!indexList.isEmpty()) {
165+
indexList.sort((o1, o2) -> o2 - o1);
166+
int index = indexList.get(0);
167+
root = nodeList.get(index);
168+
if (root.left != null && root.right != null) {
169+
nodeList.add(index + 1, root.right);
170+
nodeList.add(index, root.left);
171+
indexList.add(index + 2);
172+
indexList.add(index);
173+
} else if (root.left != null) {
174+
nodeList.add(index, root.left);
175+
indexList.add(index);
176+
} else if (root.right != null) {
177+
nodeList.add(index + 1, root.right);
178+
indexList.add(index + 1);
179+
}
180+
indexList.remove(0);
181+
}
182+
for (TreeNode node : nodeList) {
183+
resList.add(node.val);
184+
}
185+
return resList;
186+
}
136187
}

‎leetcode_Java/Solution0144.java‎

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -121,4 +121,54 @@ public List<Integer> preorderTraversal(TreeNode root) {
121121
}
122122
return list;
123123
}
124+
}
125+
126+
127+
/*
128+
* 迭代思路：
129+
* 1、定义数据结构：结果列表存放排序节点值；节点列表按序存放节点；索引列表存放未判断是否有左右子节点的节点
130+
* 2、数据结构初始化：根节点存入节点列表；索引0存入索引列表
131+
* 3、迭代逻辑：
132+
* 1）索引列表不为空时，说明有节点未判断是否有左右子节点，循环遍历索引列表
133+
* 2）索引列表降序排序，取出最大索引，对该索引的节点进行操作。先处理靠右边的节点，可以防止插入节点时影响了节点列表其他节点的位置
134+
* 3）是否有子节点存在四种情况：有左右节点、只有右节点、只有左节点、没有左右节点。要分别处理，不同情况节点最终索引位置不同
135+
* 4）前序遍历：
136+
* 先插入右节点，再插入左节点
137+
* 插入左右节点都是在根节点右边插入，其他结点右移一位
138+
* 5）最大索引的节点判断完左右节点后，移除索引列表的最大索引
139+
* 6）最终节点列表按序排序，遍历结点列表，将节点值存入结果列表
140+
* */
141+
class Solution {
142+
public List<Integer> preorderTraversal(TreeNode root) {
143+
List<Integer> resList = new ArrayList<>();
144+
if (root == null) {
145+
return resList;
146+
}
147+
List<TreeNode> nodeList = new ArrayList<>();
148+
List<Integer> indexList = new ArrayList<>();
149+
nodeList.add(root);
150+
indexList.add(0);
151+
while(!indexList.isEmpty()) {
152+
indexList.sort((o1, o2) -> o2 - o1);
153+
int index = indexList.get(0);
154+
root = nodeList.get(index);
155+
if (root.left != null && root.right != null) {
156+
nodeList.add(index + 1, root.right);
157+
nodeList.add(index + 1, root.left);
158+
indexList.add(index + 2);
159+
indexList.add(index + 1);
160+
} else if (root.left != null) {
161+
nodeList.add(index + 1, root.left);
162+
indexList.add(index + 1);
163+
} else if (root.right != null) {
164+
nodeList.add(index + 1, root.right);
165+
indexList.add(index + 1);
166+
}
167+
indexList.remove(0);
168+
}
169+
for (TreeNode node : nodeList) {
170+
resList.add(node.val);
171+
}
172+
return resList;
173+
}
124174
}

‎leetcode_Java/Solution0145.java‎

Lines changed: 51 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -77,4 +77,54 @@ public List<Integer> postorderTraversal(TreeNode root) {
7777

7878
/*
7979
* 迭代思路：144题，前序遍历的迭代思路，结果数组反转
80-
* */
80+
* */
81+
82+
83+
/*
84+
* 迭代思路：
85+
* 1、定义数据结构：结果列表存放排序节点值；节点列表按序存放节点；索引列表存放未判断是否有左右子节点的节点
86+
* 2、数据结构初始化：根节点存入节点列表；索引0存入索引列表
87+
* 3、迭代逻辑：
88+
* 1）索引列表不为空时，说明有节点未判断是否有左右子节点，循环遍历索引列表
89+
* 2）索引列表降序排序，取出最大索引，对该索引的节点进行操作。先处理靠右边的节点，可以防止插入节点时影响了节点列表其他节点的位置
90+
* 3）是否有子节点存在四种情况：有左右节点、只有右节点、只有左节点、没有左右节点。要分别处理，不同情况节点最终索引位置不同
91+
* 4）后序遍历：
92+
* 先插入右节点，再插入左节点
93+
* 插入左右节点都是替代了根节点的位置，其他结点右移一位
94+
* 5）最大索引的节点判断完左右节点后，移除索引列表的最大索引
95+
* 6）最终节点列表按序排序，遍历结点列表，将节点值存入结果列表
96+
* */
97+
class Solution {
98+
public List<Integer> postorderTraversal(TreeNode root) {
99+
List<Integer> resList = new ArrayList<>();
100+
if (root == null) {
101+
return resList;
102+
}
103+
List<TreeNode> nodeList = new ArrayList<>();
104+
List<Integer> indexList = new ArrayList<>();
105+
nodeList.add(root);
106+
indexList.add(0);
107+
while(!indexList.isEmpty()) {
108+
indexList.sort((o1, o2) -> o2 - o1);
109+
int index = indexList.get(0);
110+
root = nodeList.get(index);
111+
if (root.left != null && root.right != null) {
112+
nodeList.add(index, root.right);
113+
nodeList.add(index, root.left);
114+
indexList.add(index + 1);
115+
indexList.add(index);
116+
} else if (root.left != null) {
117+
nodeList.add(index, root.left);
118+
indexList.add(index);
119+
} else if (root.right != null) {
120+
nodeList.add(index, root.right);
121+
indexList.add(index);
122+
}
123+
indexList.remove(0);
124+
}
125+
for (TreeNode node : nodeList) {
126+
resList.add(node.val);
127+
}
128+
return resList;
129+
}
130+
}

0 commit comments

Comments
 (0)