（Java）leetcode-145 Binary Tree Postorder Traversal (二叉树的后序遍历)

r囧r小猫 2023-02-21 06:09 4阅读 0赞

更多LeetCode题解，可移步[我的解题记录][Link 1]，持续更新中~

# 题目描述 #

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

示例:

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

1
        \
         2
        /
       3

输出: \[3,2,1\]  
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

# 思路 #

递归算法就不贴了，是树的题目的基础算法。  
至于迭代算法，参考[leetcode-589、590 N-ary Tree Traversal（N叉树遍历）][leetcode-589_590 N-ary Tree Traversal_N]中的“N叉树的后续遍历”，二叉树的版本思路是一样的。

树的后序遍历（下图的蓝色箭头） = 树的**镜像**的前序遍历 (下图的红色箭头) 的**逆** 。  
二叉树是一种特定的树，当然也符合这个结论。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3o3MTQ0MDU0ODk_size_16_color_FFFFFF_t_70]  
我们知道了二叉树前序遍历的迭代解法，就是借助栈，某节点出栈时， 从右到左 将此节点的孩子入栈。  
现在变成了 镜像问题 ，那么出栈时， 从左到右  将节点的孩子入栈，最后需要求逆，将结果集进行一次翻转就能得到正确结果了。

在最后反转ArrayList的代码：

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

或是是使用LinkedList，在添加元素到结果集时，使用addFirst()方法，从list的头部添加元素，最后就不用整体翻转了：

class Solution { 
        public List<Integer> postorderTraversal(TreeNode root) { 
    		List<Integer> res = new LinkedList<>();
    		if (root == null) return res;
    
    		Stack<TreeNode> stack = new Stack<>();
            stack.add(root);
    		while(!stack.isEmpty()) { 
                root = stack.pop();
                // 从列表的头部添加
                res.addFirst(root.val);
    	        if (root.left != null) stack.push(root.left);
    	        if (root.right != null) stack.push(root.right);
            }
            return res;
        }
    }

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

[Link 1]: https://github.com/MagicalPiggy/leetcode
[leetcode-589_590 N-ary Tree Traversal_N]: https://blog.csdn.net/z714405489/article/details/106474012
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3o3MTQ0MDU0ODk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200630142813167.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3o3MTQ0MDU0ODk=,size_16,color_FFFFFF,t_70