一文搞懂二叉树后序遍历的三种方法

系列文章：

相关题目：
145. 二叉树的后序遍历

先序遍历结果为：4 5 2 6 7 3 1

总体上分为两种框架，递归框架和非递归框架，递归框架又分为两种思路：分解思路和遍历思路。

• 递归
  1、分解思路 【分解为子问题】
  2、遍历思路 【更新外部变量】
• 非递归
  3、借助栈

下面代码对三种方法逐一实现。

class PostorderTraversal:
    """
    145. 二叉树的后序遍历
    https://leetcode.cn/problems/binary-tree-postorder-traversal/
    """

    def solution1(self, root):
        """
        前序遍历【分解思路 -- 子问题】
        递归函数需要有返回值，然后将左子树的返回值、右子树的返回值以及根节点的值，按照顺序拼接起来即可。
        通常为自底向上求解
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        return self.solution1(root.left) + self.solution1(root.right) + [root.val]

    def solution1_1(self, root):
        """
        分解思路，同上
        :param root:
        :return:
        """
        res = []
        if not root:
            return []

        res.extend(self.solution1_1(root.left))
        res.extend(self.solution1_1(root.right))
        res.append(root.val)

        return res

    def solution2(self, root):
        """
        遍历思路，一般需要借助递归函数，递归函数没有返回值，靠更新外部变量得到结果
        :param root:
        :return:
        """
        self.res = []
        self.traverse(root)
        return self.res

    def traverse(self, node):
        if not node:
            return

        self.traverse(node.left)
        self.traverse(node.right)
        self.res.append(node.val)

    def solution3(self, root):
        """
        非递归思路，借助栈 实现
        :param root:
        :return:
        """
        res = []
        if not root:
            return res
        else:
            stk1 = []
            stk2 = []
            cur = root
            while stk1 or cur:

                while cur:
                    stk1.append(cur)
                    stk2.append(cur)
                    cur = cur.right

                cur = stk1.pop()
                cur = cur.left

            while stk2:
                res.append(stk2.pop().val)

        return res