目录
1.题目内容
2.用递归实现后序遍历
2.1解题思路
2.2代码
3.用迭代实现后序遍历
3.1解题思路
3.2代码
1.题目内容
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
示例 1：
输入：root = [1,null,2,3]
输出：[3,2,1]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
2.用递归实现后序遍历
2.1解题思路
后序遍历：左右根
递归：一种调用自己的循环
先递归的遍历左子树，再递归的遍历右子树，最后输出根节点。此方法是将以root为根的二叉树进行后序遍历，将每一个节点套用此方法。
1.重复的子问题。
先遍历左子树，再遍历右子树，再输出根节点。
2.终止条件
if(root==null){
return;
}2.2代码
public void postOrder(TreeNode root){
if(root==null){
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val+" ");
}3.用迭代实现后序遍历
3.1解题思路
后序遍历：左右根
递归问题可以用栈来解决，将这个栈模拟出来就是迭代。引入一个cur引用，对于后序遍历的根节点来说，cur要经过此节点三次，才能打印根节点。
第一次：从根节点开始去向左子树
第二次：从左子树回来，经过根节点，去向右子树
第三次：从右子树回来，去到根节点
如何判断cur经过了根节点三次呢？
在这里引入一个标记位prev，描述上一个被完全访问的节点是谁（当cur从某一个根节点的右子树返回时，此时这个右子节点已经被完全访问，使prev=cur.right，此时可以输出根节点）
步骤：
1.初始化一个空栈，cur引用一直向左子树遍历，走到头。同时将当前节点入栈。
while(cur!=null){
stack.push(cur);
cur=cur.left;
}
2.当前栈顶元素无左右子树，为叶子节点(将D的左右子树都访问过后再返回到D为第三次经过D节点)，弹出栈顶元素。即cur.right==null时，可以输出根节点值。
cur=stack.pop();
list.add(cur.val);
3.此时栈顶元素为B，右子树不为空，所以弹出后需要再次将它入栈。再接着将B的右孩子E入栈，E的左孩子为空，右孩子不为空，所以将E出栈再入栈。E的右孩子H左右孩子都为空，，将H入栈之后输出。但是当cur返回到E时，E的右孩子依旧不为空，此时会陷入到E和H的循环中去，所以这里引入一个标记位prev,描述上一个被访问完毕的元素。当右孩子为标记位时，说明此元素被访问完毕，直接弹出。
//右子树为空或已经被标记（访问结束）
if(root.right==null || prev==cur.right){
//输出根节点,此时可以加入标记位
list.add(cur.val);
prev=cur;
//当前树访问结束，不用再压入栈中，将cur置空，此时cur从当前栈中取元素
cur=null;
}else{
//右子树不为空，访问右子树
stack.push(cur);
cur=cur.right;
}
4.此时让cur置空，使cur指向栈顶元素，否则cur会指向步骤1的内容，访问左孩子。cur置空后指向栈顶元素E，E的左孩子为空，右孩子为标记位，所以直接输出。
5.prev此时指向E，将cur置空，此时cur指向栈顶元素B，继续上述步骤。文章来源：https://www.toymoban.com/news/detail-483084.html
文章来源地址https://www.toymoban.com/news/detail-483084.html
3.2代码
public List<Integer>postorderTraversal(TreeNode root){
//初始化一个整形动态数组
List<Integer>list=new ArrayList<>();
//base case
if(root==null){
return list;
}
//定义一个引用cur指向root，当前要访问的节点
TreeNode cur=root;
//上一个完全访问结束的节点
TreeNode prev=null;
//初始化一个空栈
Deque<TreeNode>stack=new LinkedList<>();
while(cur!=null || !stack.isEmpty()){
//先一路向左
while(cur!=null){
stack.push(cur);
cur=cur.left;
}
//此时左子树为空，出栈
cur=stack.pop();
if(cur.right==null || prev==cur.right){
//此时右子树为空或者已经访问结束
list.add((int)cur.val);
//更新prev为当前已被打印的节点
prev=cur;
//将cur置空，下一次循环从栈顶取元素
cur=null;
}else{
//继续访问右子树
stack.push(cur);
cur=cur.right;
}
}
return list;
}到了这里，关于用java实现二叉树的后序遍历（递归和迭代）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
