二叉树的后序遍历

Leetcode Link: 145. 二叉树的后序遍历 - 力扣（LeetCode） (leetcode-cn.com)

题目

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

解法一

思路：递归完成

题解： 利用全局变量，就是根据左程云的递归序进行的改进操作

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def recur(cur):
            if not cur:
                return
            recur(cur.left)
            recur(cur.right)
            res.append(cur.val)
        ## 其实这里不用判断root也行，是吧？因为直接返回的res也是空列表
        res = []
        recur(root)
        return res
 

使用局部变量的方法，获取到两个子树的信息后再统一处理

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        left = self.postorderTraversal(root.left)
        right = self.postorderTraversal(root.right)
            
        res = []
        res.extend(left)
        res.extend(right)
        res.append(root.val)
        return res

解法二

思路：迭代

后序遍历_

后序的顺序是【左、右、头】，这就相当于是【头、右、左】顺序的逆序，因此只需要把先序的想法稍微改变一下，再逆序打印，即可完成后序遍历的非递归实现。

为了实现“逆序”，我们需要另外创建一个收集栈，将原栈打印的东西存起来，最后再将收集栈中的东西一一弹出，即完成了“逆序”

创建一个栈，首先把根节点扔进去，然后每次：

1. 从栈中弹出一个节点 cur
2. 将 cur 压入“收集栈”（对于先序操作中的打印操作）
3. 把 cur 的左孩子压到栈里去，再把 cur 的右孩子压到栈里去（即先左后右压到栈里去）
4. 重复1-3步
5. 依次弹出“收集栈”里的内容

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        stack = []
        stack.append(root)
        res = []
        while(len(stack)>0):
            cur = stack.pop()
            res.append(cur.val)
            if cur.left: stack.append(cur.left)
            if cur.right: stack.append(cur.right)
        return res[::-1] # 注意逆序返回

指向原始笔记的链接

解法三

思路：Morris 遍历 todo

题解：

启发和联系