二叉树题解--java|二叉树后序遍历（迭代+递归）-java java|算法|leetcode|蓝桥杯

目录

一、题目
二、后序遍历讲解
三、递归实现后序遍历
1、递归思路
2、代码实现
四、迭代实现后序遍历
1、迭代思路
2、代码实现
五、欢迎访问我的java二叉树专栏

一、题目

1、链接：力扣
2、内容：
给你一棵二叉树的根节点 root ，返回其节点值的后序遍历。

示例 1：

文章图片

输入：root = [1,null,2,3] 输出：[3,2,1]

二、后序遍历讲解

（1）后序遍历下图二叉树，结果： 5--2--6--3--1

文章图片

（2）后序遍历顺序：左右中

三、递归实现后序遍历 1、递归思路

（1）确定递归放回值以及参数：根据题目需要返回遍历的节点，所以需要List集合存储节点的值，同时需要将二叉树头节点传入；

postOrder(TreeeNode root,List result)

（2）确定递归终止条件：遍历二叉树节点为空，表明已经无节点，直接return

if(root==null) return;

（3）确定递归逻辑：递归顺序为左，右，中，递归开始时，先将根节点添加List集合，然后遍历左子树，最后遍历右子树。

postOrder(treeNode.left,result); //左 postOrder(treeNode.right,result); //右 result.add(treeNode.val); //中

2、代码实现

public List preorderTraversal(TreeNode root) { List result=new ArrayList<>(); postOrder(root,result); return result; }//后序遍历 public static void postOrder(TreeNode treeNode,List result){ if (treeNode==null){ return; } postOrder(treeNode.left,result); //左 postOrder(treeNode.right,result); //右 result.add(treeNode.val); //中 }

四、迭代实现后序遍历 1、迭代思路

（1）借助栈实现迭代遍历，先序遍历为中左右，改变顺序为：中右左，然后反转结果，即为后序遍历：左右中；
（2）判断二叉树是否为空，不为空，头节点入栈

文章图片

（3）栈不为空，栈顶元素弹出，并将元素添加到list集合，判断左子树是否为空，不为空入栈，判读右子树是否为空，不为空入栈

文章图片

（4）重复以上操作

文章图片

文章图片

文章图片

文章图片

最后到这里，不要忘记将集合反转

2、代码实现

class Solution { public List postorderTraversal(TreeNode treeNode) { List result=new ArrayList<>(); Stack stack=new Stack<>(); if(treeNode==null) return result; stack.push(treeNode); while (!stack.isEmpty()){ TreeNode root=stack.pop(); result.add(root.val); if (root.left!=null){ stack.push(root.left); } if (root.right!=null){ stack.push(root.right); } }Collections.reverse(result); for (Integer integer : result) { System.out.println(integer); } return result; } }

五、欢迎访问我的java二叉树专栏