145. Binary Tree Postorder Traversal

题目描述和难度

  • 题目描述：

给定一个二叉树，返回它的 后序 遍历。

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3

输出: [3,2,1]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

思路分析

求解关键：非递归的写法其实是个套路，三种遍历都可以使用这个模板完成。

参考解答

参考解答1：递归写法

public class Solution2 {

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

    /**
     * 递归的方式后续遍历二叉树
     * @param root
     * @return
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        postorder(root);
        return result;

    }

    private void postorder(TreeNode root) {
        if(root!=null){
            postorder(root.left);
            postorder(root.right);
            result.add(root.val);
        }
    }
}

参考解答

参考解答2：非递归写法

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

enum UseType {
    RECURSION,
    ADD
}

class Command {
    UseType useType;
    TreeNode treeNode;

    public Command(UseType useType, TreeNode treeNode) {
        this.useType = useType;
        this.treeNode = treeNode;
    }
}


public class Solution {

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result  =new ArrayList<>();
        if(root==null){
            return result;
        }
        Stack<Command> stack = new Stack<>();
        stack.add(new Command(UseType.RECURSION,root));

        while (!stack.isEmpty()){
            Command command = stack.pop();

            if(UseType.ADD == command.useType){
                result.add(command.treeNode.val);
            }else {
                assert UseType.RECURSION == command.useType;
                stack.push(new Command(UseType.ADD,command.treeNode));
                if(command.treeNode.right!=null){
                    stack.push(new Command(UseType.RECURSION,command.treeNode.right));
                }
                if(command.treeNode.left!=null){
                    stack.push(new Command(UseType.RECURSION,command.treeNode.left));
                }
            }
        }
        return result;
    }

}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0145-binary-tree-postorder-traversal ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。