算法打卡Day18

我知道，生活越接近平淡，内心越接近绚烂。经历了世事的智者，终于领悟到，太过用力太过张扬的东西，一定是虚张声势的。而内心的安宁才是真正的安宁，它更干净、更纯粹，更接近那叫灵魂的地方。

Leetcode原题

145.二叉树后序遍历

思路

前面做了前序遍历、中序遍历，不出意外还有后序遍历。

后序遍历（LRD）是二叉树遍历的一种，也叫做后根遍历、后序周游，可记做左右根。后序遍历有递归算法和非递归算法两种。在二叉树中，先左后右再根，即首先遍历左子树，然后遍历右子树，最后访问根结点。

方法一 递归实现

class Solution {
    public List postorderTraversal(TreeNode root) {
    //中序遍历： 左中右
         List res =new ArrayList<>();
         accessTree(root, res);
        return res;
    }


    public void accessTree(TreeNode root, List res){
        if(root == null){
            return;
        }
       //递归左右中
        accessTree(root.left,res);
         accessTree(root.right,res);
          res.add(root.val);
    }
}

递归实现通常很简单，但是会让你忽律很多的细节。

方法二 迭代

方法一的递归函数我们也可以用迭代的方式实现，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其他都相同。后序遍历迭代较为复杂一些。具体实现可以看下面的代码。

class Solution {
    public List postorderTraversal(TreeNode root) {
     //后序序遍历： 跟节点在最后，左右中
         List res =new ArrayList<>();
         Deque 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套哦~