Leetcode原题
思路
前面做了前序遍历、中序遍历，不出意外还有后序遍历。
后序遍历（LRD）是二叉树遍历的一种，也叫做后根遍历、后序周游，可记做左右根。后序遍历有递归算法和非递归算法两种。在二叉树中，先左后右再根，即首先遍历左子树，然后遍历右子树，最后访问根结点。
方法一 递归实现
class Solution { public List<Integer> postorderTraversal(TreeNode root) { //中序遍历： 左中右 List<Integer> res =new ArrayList<>(); accessTree(root, res); return res; } public void accessTree(TreeNode root, List<Integer> res){ if(root == null){ return; } //递归左右中 accessTree(root.left,res); accessTree(root.right,res); res.add(root.val); } }
递归实现通常很简单，但是会让你忽律很多的细节。
方法二 迭代
方法一的递归函数我们也可以用迭代的方式实现，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其他都相同。后序遍历迭代较为复杂一些。具体实现可以看下面的代码。
class Solution { public List<Integer> postorderTraversal(TreeNode root) { //后序序遍历： 跟节点在最后，左右中 List<Integer> res =new ArrayList<>(); Deque<TreeNode> statck =new LinkedList<>(); TreeNode preNode=null; while(root!=null || !statck.isEmpty()){ while(root!= null){ //先添加跟节点 statck.push(root); //然后左节点入栈 root= root.left; } //出栈 root = statck.pop(); //当前节点无右子树，或右子树等于前一个变量节点 if (root.right == null || root.right ==preNode){ res.add(root.val); preNode =root; root =null; }else{ statck.push(root); root = root.right; } } return res; } }
有兴趣的老爷，还可以关注我的公众号【一起收破烂】，回复【006】获取 最新java面试资料以及简历模型120套哦~
