算法打卡Day18_leetcode _145. 二叉树的后序遍历

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;
    }
}