本文内容来自于代码随想录
中、左、右
void preorder(TreeNode root) {
process(root); // 处理中间节点
preorder(root.left);
preorder(root.right);
}
左、中、右
void inorder(TreeNode root) {
preorder(root.left);
process(root); // 处理中间节点
preorder(root.right);
}
左、右、中
void postorder(TreeNode root) {
preorder(root.left);
preorder(root.right);
process(root); // 处理中间节点
}
从上到下、从左到右(用到队列)
// bfs记录每一层的节点
List<List<Integer>> bfs(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (root != null && !q.isEmpty()) {
int cnt = q.size();
List<Integer> temp = new ArrayList<>();
// 每次把队列里的全部弹出来,这样队列里永远都是同一层的节点
while (cnt > 0) {
TreeNode head = q.poll();
temp.add(head.val);
cnt -- ;
if (head.left != null) q.offer(head.left);
if (head.right != null) q.offer(head.right);
}
ans.add(temp);
}
return ans;
}
中、左、右(先序)-> 中、右、左 -> 左、右、中(后序)。所以如果要得到后序的结果,即先按先序的操作去迭代遍历(需要把左右换成右左),然后把结果进行反转即可(中右左 反转成 左右中)。
if (root == null) return -1; // 判断当前节点
if (root.left == null && root.right == null) { // 判断是否为叶子节点
}
中序遍历就是从小到大排序的结果。
List<Integer> list = new ArrayList<>();
void inorder(TreeNode root) {
if (root == null) return ;
inorder(root.left);
list.add(root.val);
inorder(root.right);
}
for(int x : list) System.out.println(x); // 从小到大排序的结果
● 确定递归函数返回值以及参数
● 确定终止条件
● 确定单层递归逻辑