145. 二叉树的后序遍历

太过爱你忘了你带给我的痛 2022-12-09 02:00 146阅读 0赞

# 题目： #

[145. 二叉树的后序遍历][145.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]

# 题解： #

**[144. 二叉树的前序遍历][144.]  
[94. 二叉树的中序遍历][94.]  
[145. 二叉树的后序遍历][145. 1]**

## 1. 题解一：递归后序遍历 ##

第一种解决方法是使用递归。这是经典的方法，直截了当。我们可以定义一个辅助函数来实现递归。

## 2. 题解二：迭代后序遍历 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 1]

# 代码： #

## 1. 代码一：递归后序遍历 ##

/** * code145 */
    
    import java.util.*;
    
    public class code145 { 
    
        // 解法一：递归
        public static List<Integer> postorderTraversal(TreeNode root) { 
            List<Integer> res = new ArrayList<>();
            postorder(root, res);
            return res;
        }
    
        public static void postorder(TreeNode root, List<Integer> res) { 
            if (root == null) { 
                return;
            }
            postorder(root.left, res);
            postorder(root.right, res);
            res.add(root.val);
        }
    
        public static void main(String[] args) { 
            // 根据给定的数组创建一棵树
            Integer nums[] = {  1, null, 2, 3 };
            TreeNode tree = ConstructTree.constructTree(nums);
            // 将刚刚创建的树打印出来
            TreeOperation.show(tree);
    
            // Integer nums[] = { 5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1 };
            // TreeNode tree = ConstructTree.constructTree(nums);
            // ConstructTree.postorder(tree);
            // System.out.println();
            // ConstructTree.midOrder(tree);
            // System.out.println();
            // ConstructTree.aftOrder(tree);
            // System.out.println();
    
            // TreeOperation.show(tree);
    
            System.out.println("后序遍历：");
            List<Integer> list = postorderTraversal(tree);
            for (int i = 0; i < list.size(); i++) { 
                System.out.print(list.get(i) + " ");
            }
            System.out.println();
        }
    }

## 2. 代码二：迭代后序遍历 ##

/** * code145 */
    
    import java.util.*;
    
    public class code145 { 
    
        // 解法二：迭代
        public static List<Integer> postorderTraversal(TreeNode root) { 
            List<Integer> res = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root;
            TreeNode last = null;
            while (cur != null || !stack.isEmpty()) { 
                while (cur != null) { 
                    stack.push(cur);
                    cur = cur.left;
                }
                cur = stack.peek();
                if(cur.right == null || cur.right == last)
                { 
                    res.add(cur.val);
                    stack.pop();
                    // 记录上一个访问的节点
                    // 用于判断“访问根节点之前，右子树是否已访问过”
                    last = cur;
                    // 表示不需要转向，继续弹栈
                    cur = null;
                }
                else
                { 
                    cur = cur.right;
                }
            }
            return res;
        }
    
        public static void main(String[] args) { 
            // 根据给定的数组创建一棵树
            Integer nums[] = {  1, null, 2, 3 };
            TreeNode tree = ConstructTree.constructTree(nums);
            // 将刚刚创建的树打印出来
            TreeOperation.show(tree);
    
            // Integer nums[] = { 5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1 };
            // TreeNode tree = ConstructTree.constructTree(nums);
            // ConstructTree.postorder(tree);
            // System.out.println();
            // ConstructTree.midOrder(tree);
            // System.out.println();
            // ConstructTree.aftOrder(tree);
            // System.out.println();
    
            // TreeOperation.show(tree);
    
            System.out.println("后序遍历：");
            List<Integer> list = postorderTraversal(tree);
            for (int i = 0; i < list.size(); i++) { 
                System.out.print(list.get(i) + " ");
            }
            System.out.println();
        }
    }

# 参考： #

1.  [【刷题】二叉树非递归遍历][Link 1]
2.  [二叉树后序遍历的两种易写的非递归写法][Link 2]
3.  [二叉树的后序遍历][Link 3]
4.  [迭代解法，时间复杂度 O(n)，空间复杂度 O(n)][O_n_ O_n]
5.  [帮你对二叉树不再迷茫，彻底吃透前中后序递归法（递归三部曲）和迭代法（不统一写法与统一写法）][Link 4]
6.  [二叉树遍历通解（递归和迭代解法）- 完全模拟递归][-]
7.  [阿里面试题，只用栈去做二叉树的后序遍历，不能依靠队列去状态比较][Link 5]
8.  [二叉树后序非递归遍历\[两种主流写法\]][Link 6]
9.  [详细通俗的思路分析，多解法][Link 7]
10. [史上最全遍历二叉树详解][Link 8]
11. [递归和非递归两种解决方式][Link 9]
12. [二叉树的后序遍历（迭代法）][Link 10]

[145.]: https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/7cfa22dd20384f00bed5dcf7fd63efb4.png
[144.]: https://zhangyx.blog.csdn.net/article/details/108705982
[94.]: https://zhangyx.blog.csdn.net/article/details/104304658
[145. 1]: https://zhangyx.blog.csdn.net/article/details/108706556
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/d875355f2dcd4791a6dd4cb2a0923348.png
[Link 1]: https://juejin.im/post/6844903503807119374
[Link 2]: https://zhuanlan.zhihu.com/p/80578741
[Link 3]: https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/er-cha-shu-de-hou-xu-bian-li-by-leetcode/
[O_n_ O_n]: https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/die-dai-jie-fa-shi-jian-fu-za-du-onkong-jian-fu-za/
[Link 4]: https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/bang-ni-dui-er-cha-shu-bu-zai-mi-mang-che-di-chi-t/
[-]: https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/bian-li-tong-jie-by-long_wotu/
[Link 5]: https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/a-li-mian-shi-ti-zhi-yong-zhan-qu-zuo-er-cha-shu-d/
[Link 6]: https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/er-cha-shu-hou-xu-fei-di-gui-bian-li-liang-chong-z/
[Link 7]: https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by--34/
[Link 8]: https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/leetcodesuan-fa-xiu-lian-dong-hua-yan-shi-xbian--2/
[Link 9]: https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/javazui-jian-dan-de-yi-chong-fang-shi-jiu-shi-di-g/
[Link 10]: https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/er-cha-shu-de-hou-xu-bian-li-die-dai-fa-by-da-da-m/