- 系列文章目录
- 题录
- 144. 二叉树的前序遍历
- 递归写法
- 迭代写法
- 94. 二叉树的中序遍历
- 递归写法
- 迭代写法
- 145. 二叉树的后序遍历
- 递归写法
- 迭代写法--1
- 迭代写法--2
刷题笔记(一)–数组类型:二分法
刷题笔记(二)–数组类型:双指针法
刷题笔记(三)–数组类型:滑动窗口
刷题笔记(四)–数组类型:模拟
刷题笔记(五)–链表类型:基础题目以及操作
刷题笔记(六)–哈希表:基础题目和思想
刷题笔记(七)–字符串:经典题目
刷题笔记(八)–双指针:两数之和以及延伸
刷题笔记(九)–字符串:KMP算法
刷题笔记(十)–栈和队列:基础题目
刷题笔记(十一)–栈和队列:Top-K问题
刷题笔记(十二)–复习:排序算法
题目链接如下:
144. 二叉树的前序遍历
题目截屏如下:
解法如下:
public class 前序遍历 {
public List preorderTraversal(TreeNode root) {
//构造一个List用来返回
List list = new ArrayList<>();
//然后开始前序遍历
preorderTraversal(list,root);
return list;
}
public void preorderTraversal(List list,TreeNode root){
//如果为空就直接返回
if(root == null){
return;
}
//前序遍历:根节点 --> 左子树 --> 右子树
list.add(root.val);
preorderTraversal(list,root.left);
preorderTraversal(list,root.right);
}
}
迭代写法
public List94. 二叉树的中序遍历preorderTraversal(TreeNode root) { List list = new ArrayList<>();//构造一个list用来接收root值 Stack stack = new Stack<>();//构造一个栈用来前序遍历 //不为空就把root入栈 if(root != null){ stack.push(root); } //栈不为空就开始遍历 while(!stack.isEmpty()){ TreeNode node = stack.pop(); list.add(node.val); //栈的特性:先进后出,所以右子树先入栈后出 if(node.right != null){ stack.push(node.right); } //左子树后入栈先出 if(node.left != null){ stack.push(node.left); } } return list; }
题目链接如下:
94. 二叉树的中序遍历
题目截图如下:
递归写法递归写法和上面的差不多,就是调换了一下位置
public class 中序遍历_递归写法 {
public List inorderTraversal(TreeNode root) {
List list = new ArrayList<>();
inorderTraversal(list,root);
return list;
}
public void inorderTraversal(List list,TreeNode root) {
if(root == null){
return;
}
inorderTraversal(list,root.left);
list.add(root.val);
inorderTraversal(list, root.right);
}
}
迭代写法
public class 中序遍历_迭代写法 {
public List inorderTraversal(TreeNode root) {
Stack stack = new Stack<>();
List list = new ArrayList<>();
TreeNode cur = root;
//栈为空并且cur == null的时候就遍历完毕
while(!stack.isEmpty() || cur != null){
//首先就是往左走,一直往左走,走到没有地方走为止
if(cur != null){
stack.push(cur);
cur = cur.left;
}else{//如果说左子树为null的时候,就把当前节点值加入,然后遍历右子树的左子树
cur = stack.pop();
list.add(cur.val);
cur = cur.right;
}
}
return list;
}
}
145. 二叉树的后序遍历
题目链接如下:
145. 二叉树的后序遍历
题目截屏如下:
递归写法public class 后序遍历_递归 {
public List postorderTraversal(TreeNode root) {
List list = new ArrayList<>();
postorderTraversal(list,root);
return list;
}
public void postorderTraversal(List list,TreeNode root) {
if(root == null){
return;
}
postorderTraversal(list,root.left);
postorderTraversal(list,root.right);
list.add(root.val);
}
}
迭代写法–1
这里的话其实就是把前序遍历得到的list翻转一下
public class 后序遍历_迭代 {
public List postorderTraversal(TreeNode root) {
List list = new ArrayList<>();
Stack stack = new Stack<>();
if(root != null) {
stack.push(root);
}
while(!stack.empty()){
TreeNode node = stack.pop();
list.add(node.val);
if(node.left != null){
stack.push(node.left);
}
if(node.right != null){
stack.push(node.right);
}
}
Collections.reverse(list);
return list;
}
}
迭代写法–2
public class 后续遍历_迭代2 {
public List postorderTraversal(TreeNode root) {
List res = new ArrayList<>();
Stack stack = new Stack<>();
// cur 用来遍历
TreeNode cur = root;
// prev 用来记录上次遍历的个结点
TreeNode prev = null;
while (cur != null || !stack.isEmpty()) {
if (cur != null) {
stack.add(cur);
cur = cur.left;
} else {
cur = stack.pop();
if (cur.right != null && cur.right != prev) {
// 有右子树并且右子树没遍历,需放回根结点到栈中
stack.push(cur);
// 接下来遍历右子树
cur = cur.right;
} else {
// 没有右子树,或者右子树被遍历过,
res.add(cur.val);
// 更新前指针
prev = cur;
// 以该结点的子树都已遍历,下次需要从栈中取父亲结点向上遍历,所以 cur == null
cur = null;
}
}
}
return res;
}
}



