LeetCode_14_BinaryTreePostOrderTraversal

1. question: 二叉树的后续遍历（简单）

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal

示例 1：

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

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示：

树中节点的数目在范围 [0, 100] 内
-100 <= Node.val <= 100

2. answers

和前面一样，二叉树的后序遍历也分为递归和迭代两种方法。

2.1 递归解法

代码如下所示：

public class Solution_0012 {

    public static void recurive(TreeNode root, List<Integer> result){

        if(root != null) {
            recurive(root.left, result);
            recurive(root.right, result);
            result.add(root.val);
        }
    }

    // 递归
    public static List<Integer> postorderTraversal(TreeNode root) {

        List<Integer> result = new ArrayList<>();

        recurive(root, result);

        return result;
    }

    public static void main(String[] args) {
        TreeNode tn1 = new TreeNode(3);
        TreeNode tn2 = new TreeNode(2, tn1, null);
        TreeNode root = new TreeNode(1, null, tn2);

//        List<Integer> integers = preorderTraversal(root);
//        List<Integer> integers = preorderTraversal(null);
//        List<Integer> integers = preorderTraversal(new TreeNode(1));
//        for(Integer i : integers){
//            System.out.println(i);
//        }

        List<Integer> integers = postorderTraversal(root);
//        List<Integer> integers = postorderTraversalPlus(root);
        for(Integer i: integers){
            System.out.println(i);
        }
    }
}

2.2 迭代解法

注意，后续遍历的迭代解法和前序遍历“类似”。在前序遍历中，左右子树访问顺序修改一下，即中右左，然后再将结果反转一下，就是后续遍历左右中了。

代码如下所示：

public class Solution_0012 {

    // 迭代（非递归）
    public static List<Integer> postorderTraversalPlus(TreeNode root) {

        // 注意，后续遍历（左右中）和前序遍历（中左右）的非递归写法很相似
        // 前序遍历的非递归（中左右），在入栈的时候，改变一下顺序，即中左右，那么实际访问顺序就是中右左
        // 此时，将访问顺序保存，然后再逆序就是左右中了，即后续遍历了。

        List<Integer> result = new ArrayList<>();

        Stack<TreeNode> sta = new Stack<>();

        if( root != null) {
            sta.push(root);
        }

        while(!sta.isEmpty()) {
            root = sta.pop();

            // 注意，逆序加入栈中（左右），取出来就是右左，也就是中右左，最后反转result中的即可。
            result.add(root.val);

            if(root.left != null) {
                sta.push(root.left);
            }

            if(root.right != null) {
                sta.push(root.right);
            }
        }

        // 反转结果，由 中右左 反转为 左右中。
        Collections.reverse(result);

        return result;
    }

    public static void main(String[] args) {
        TreeNode tn1 = new TreeNode(3);
        TreeNode tn2 = new TreeNode(2, tn1, null);
        TreeNode root = new TreeNode(1, null, tn2);

//        List<Integer> integers = preorderTraversal(root);
//        List<Integer> integers = preorderTraversal(null);
//        List<Integer> integers = preorderTraversal(new TreeNode(1));
//        for(Integer i : integers){
//            System.out.println(i);
//        }

//        List<Integer> integers = postorderTraversal(root);
        List<Integer> integers = postorderTraversalPlus(root);
        for(Integer i: integers){
            System.out.println(i);
        }
    }
}

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。