【LeetCode】二叉树的后序遍历

递归思想实现二叉树的后序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<Integer> list = new ArrayList<Integer>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) {
            return list;
        }
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        list.add(root.val);

        return list;
    }
}

非递归思想实现后序遍历 （借助于LinkedList实现，针对每一个处理节点，将左右节点放入nodeList，每次处理的时候处理最后一个元素即树某节点的右节点，然后使用头插插入结果中）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> list = new LinkedList<Integer>();
        if (root == null) {
            return list;
        }
        
        LinkedList<TreeNode> nodeList = new LinkedList<TreeNode>();
        nodeList.add(root);
        
        // 前序的逆序即后序遍历
        while (!nodeList.isEmpty()) {
            TreeNode p = nodeList.pollLast(); // 从nodeList取最后一个，相当于先处理右子树
            list.addFirst(p.val); // 将每一个处理节点的值使用头插的逻辑插入list

            if (p.left != null) {
                nodeList.add(p.left);
            }
            if (p.right != null) {
                nodeList.add(p.right);
            }
        }
        return list;
        
    }
}

时间复杂度：访问每个节点恰好一次，因此时间复杂度为 O(N)，其中 N 是节点的个数，也就是树的大小。
空间复杂度：取决于树的结构，最坏情况需要保存整棵树，因此空间复杂度为 O(N)