二叉树后序遍历（迭代+递归）-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<Integer> result) （2）确定递归终止条件：遍历二叉树节点为空，表明已经无节点，直接return if(root==null) return; （3）确定递归逻辑：递归顺序为左，右，中，递归开始时，先将根节点添加List集合，然后遍历左子树，最后遍历右子树。 postOrder(treeNode.left,result);//左 postOrder(treeNode.right,result);//右 result.add(treeNode.val);//中

2、代码实现

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result=new ArrayList<>();
        postOrder(root,result);
        return result;
    }

    //后序遍历
    public static void postOrder(TreeNode treeNode,List<Integer> 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<Integer> postorderTraversal(TreeNode treeNode) {
        List<Integer> result=new ArrayList<>();
        Stack<TreeNode> 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二叉树专栏