力扣 145 树的后跟遍历

题意：后跟遍历整个树

思路：

1. 用stack把头节点放入其中
2. 遍历stack，每次pop出头节点
3. 如果头节点不为空，把头节点的值加入结果，并把左子树和右子树的节点加入其中
4. 遍历完stack后，把res倒转，并返回res

思想：树的后跟遍历

复杂度：时间O（n)，空间O(n)

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            List<Integer> ret = new ArrayList<>();
            while (!stack.isEmpty()) {
                TreeNode node = stack.pop();
                if (node != null) {
                    ret.add(node.val);
                    stack.push(node.left);
                    stack.push(node.right);
                }
            }
        Collections.reverse(ret);
        return ret;
    }
}