leetcode:145. 二叉树的后序遍历(递归和非递归版)

向右看齐 2021-09-28 13:30 225阅读 0赞

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

**示例:**

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

**进阶:** 递归算法很简单，你可以通过迭代算法完成吗？

递归版本

List<Integer> resdg = new ArrayList<>();
    
        public List<Integer> postorderTraversaldg(TreeNode root) {
            if (root == null) return resdg;
            //前序遍历 左 中 右
            postorderTraversaldg(root.left);
            postorderTraversaldg(root.right);
            resdg.add(root.val);
            return resdg;
        }

迭代版本

public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            if (root == null) return res;
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            //上一个访问的节点
            TreeNode upNode = null;
            while (!stack.isEmpty()) {
                TreeNode nnode = stack.peek();
                //此处判断的意义是是否为叶子结点或者是上一次访问节点的父节点  (nnode.left == upNode ||
                if ((nnode.left == null && nnode.right == null) ||
                        (upNode != null && nnode.right == upNode)) {
                    res.add(nnode.val);
                    upNode = nnode;
                    stack.pop();
                } else {
                    //栈的特性是先进后出所以先进右再进左
                    if (nnode.right != null) stack.push(nnode.right);
                    if (nnode.left != null) stack.push(nnode.left);
                }
            }
            return res;
        }