二叉树后序遍历（迭代+递归）-java

目录

 一、题目

二、后序遍历讲解

三、递归实现后序遍历

 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二叉树专栏

https://blog.csdn.net/weixin_50616848/category_11818403.html