145. 二叉树的后序遍历 [hard]

https://leetcode-cn.com/problems/binary-tree-postorder-traversal/

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

示例:

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

输出: [3,2,1]

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

通过次数92,693 | 提交次数129,026

Third Try

2020-07-09

一个通用写法，使用一个None来标记下一个节点是否已经被使用过了。

本来更容易想到的方法是把遍历过left/right的节点进行标记，比如修改属性之类，但这样会导致操作一遍树本身都被改变了，不具有重复性。没想到可以在这个节点后面额外添加一个标记，这样很不错。同样的也可以使用tuple或是[visited, node]来进行标记，也行。

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        stack = [root]
        rv = []
        while len(stack):
            node = stack.pop()
            if node:
                stack.append(node)
                stack.append(None)
                if node.right:
                    stack.append(node.right)
                if node.left:
                    stack.append(node.left)
            else:
                node = stack.pop()
                rv.append(node.val)
        return rv 

执行用时：20 ms, 在所有 Python 提交中击败了68.00%的用户
内存消耗：12.8 MB, 在所有 Python 提交中击败了16.67%的用户

思路参考的是题解: @PualKing https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/mo-fang-di-gui-zhi-bian-yi-xing-by-sonp/

Second Try

2020-07-09

真是一个神奇的写法，思路完全按照先序排序逆着来。

先序排序是先根节点，然后左边，然后右边(按递归最容易理解)
后序排序是先左边，右边，然后根节点(按递归最容易理解)
先序排列是每次得到元素，都从尾部进入append到结果集中。
如果变成插入在结果集开头，则变成了右边，左边，根节点。
如果在遍历过程中把左边和右边对掉，那么就变成了左边，右边，根节点。
bingo, 按照先序排序两次反着来就可以了。

但其实对照完成版的代码从底层递推来想，还是很容易乱，不像先序排列那么自然。不过画个树出来，按照代码模拟一遍手工收集结果，过程仍然迷糊，但结果bingo!

思路是这样的，每个上层节点必然比后面的左右节点都要排在后面，因此一路先放根节点到结果集前部是没有问题的，也确保了前面的预设。至于左右子节点，那就在前面按顺序来，反正右节点先放，排在后面。

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        stack = [root]
        rv = []
        while len(stack):
            node = stack.pop()
            if node:
                rv.insert(0, node.val)
                stack.append(node.left)
                stack.append(node.right)
        return rv 
        

执行用时：28 ms, 在所有 Python 提交中击败了14.53%的用户
内存消耗：12.6 MB, 在所有 Python 提交中击败了16.67%

参考这题解的思路：

https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/die-dai-jie-fa-shi-jian-fu-za-du-onkong-jian-fu-za/

接下来我们思考一下前序遍历和后序遍历之间的关系：

前序遍历顺序为：根 -> 左 -> 右

后序遍历顺序为：左 -> 右 -> 根

如果1： 我们将前序遍历中节点插入结果链表尾部的逻辑，修改为将节点插入结果链表的头部

那么结果链表就变为了：右 -> 左 -> 根

如果2： 我们将遍历的顺序由从左到右修改为从右到左，配合如果1

那么结果链表就变为了：左 -> 右 -> 根

这刚好是后序遍历的顺序

基于这两个思路，我们想一下如何处理：

修改前序遍历代码中，节点写入结果链表的代码，将插入队尾修改为插入队首

修改前序遍历代码中，每次先查看左节点再查看右节点的逻辑，变为先查看右节点再查看左节点

作者：18211010139
链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/die-dai-jie-fa-shi-jian-fu-za-du-onkong-jian-fu-za/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

First Try

2020-07-08

还是想了很久才想出来的递归方法，首先是理解了什么是postorder traversal后序递归，但是不知道该怎么用dfs的方法写出来，分明是一个bfs的层级遍历，只是最后层次颠倒而已。

模拟了一下栈递归到最后的处理，终于写出了个dfs版本。对比前面的preorder和inorder，一下子就明白了为什么这三个要叫这名字。递归过程几乎一摸一样，区别仅仅是在什么时候把节点的数值放到结果列表中。

preorder先序遍历是先存储node值，然后深度遍历左侧，然后深度遍历右侧
inorder中序遍历是先深度遍历左侧，然后存储node值，然后深度遍历右侧
postorder后序遍历是先深度遍历左侧，然后深度遍历右侧，然后再存储node值

一切都是套路，知道了概念就行，不然之前只知道dfs，还不知道有三种不同的递归方式，而这对许多人来说应该是常识。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """

        seq = []
        def dfspo(root):
            if root:
                dfspo(root.left)
                dfspo(root.right) 
                seq.append(root.val)
        dfspo(root)
        return seq 

执行用时：24 ms, 在所有 Python 提交中击败了42.85%的用户
内存消耗：12.8 MB, 在所有 Python 提交中击败了16.67%的用户