Day 12：145. Binary Tree Postorder Traversal

今日题目

题目连结：145. Binary Tree Postorder Traversal
题目主题：Stack, Tree, Depth-First Search, Binary Tree

分享完 Preorder 及 Inorder 的Traversal以後，接下来是Postorder Traversal。建议还没了解过Tree观念的夥伴可以从本系列文 Day10 开始看，会对接下来的内容很有帮助。

简单说说 Postorder Traversal

在DFS（Depth-First Search）中Traversal分成三种方式：

1. Preorder
2. Inorder
3. Postorder

今天会用到的就是Postorder Traversal。
Postorder的原则是，当目前节点的两个子节点都确认过以後，才会读取目前的节点。假设资料是 tree = [5, 2, 6, 1, 3, null, 8]

上图中，每个节点上面的数字是读的顺序，而红色虚线箭头就是读的方向。Postorder排出来就会是 [1, 3, 2, 8, 6, 5]，Postorder基本上就是从右边子节点回来时，在读目前回到节点上的值。

题目解说

建议可以看看LeetCode原本的题目说明，这边是用我的方式说明题目，参考就好。

题目的目标是用Postorder的方式来读取树，依照这个Postorder的顺序将节点的值排到一个列表中，最後回传这个列表。

约束：

• 树的节点总数范围在 [0, 100]
• 100 <= Node.val <= 100

范例1

输入: root = [1,null,2,3]
输出: [3,2,1]

范例2

输入: root = []
输出: []

范例3

输入: root = [1]
输出: [1]

范例4

输入: root = [1,2]
输出: [2,1]

范例5

输入: root = [1,null,2]
输出: [2,1]

建议到这边先停下来，尝试自己解解看，若没有想法可再继续走下去。

解题的想像

文字描述

1. 写一个递回方法，这个方法要能传入前往的节点及要完成的list。
2. 每呼叫一次这个方法会往一个节点前进，
3. 这个递回会一直到走到发现没有节点才会往回走。
4. 每次从右边子节点往回走时，将目前回到节点上的值纪录到list中。
5. 最终跑完所有节点会回传一份用Postorder排出来的list。

图解过程

范例：tree = [5, 2, 6, null, 8]

下图中是实际上Traversal在走的过程，实际在想像移动过程的时候，建议在最下面的节点都补虚线的节点代表走到底了。

1. step1 跟 step3的步骤，可以观察到红色圆是要纪录到list的节点，每个要纪录的值一定会先把左、右的子节点都检查过後，才会把这个节点的值记录到list。
2. step2 及 step4 都是从右边子节点直接回到上层节点，会往右边子结点回到上层，代表左边节点一定走完了，因此右边子节点回上层以後，会纪录上层这个节点的值。
3. step5 确认整棵树走过一次以後，结束这个Traversal。
4. 走完step1 ~ step5以後，就会组成step6看到的list，这个list是过程中出现的红色圆一个一个组成的，也就是Postorder Traversal最後要回传的结果。

若因为没想法而走到这边，建议看完想像以後再给自己一次机会试一次。

程序码撰写

class Solution:
    # root 要进入的节点
    # postorder_list 最终要回传的list  
    def traversal(self, root: TreeNode, postorder_list: List[int]):
        # 没有节点往回走
        if root == None: return postorder_list
        # 前往左边子节点
        postorder_list = self.traversal(root.left, postorder_list)
        # 前往右边子节点
        postorder_list = self.traversal(root.right, postorder_list)
        # 右边子节点回来以後，将目前节点的值纪录到list中
        postorder_list.append(root.val)
        return postorder_list
    
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        return self.traversal(root, [])

希望您今天能了解到...

1. Postorder Traversal
2. 145. Binary Tree Postorder Traversal 的解题方法

若内容有什麽问题或建议欢迎一起交流：）
感谢您今天愿意花时间看完这篇文章~~~~

Next：100. same tree