我要招人

去企业版

首页 > 试题广场 >

二叉树的后序遍历

[编程题]二叉树的后序遍历

热度指数：80969 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

后序遍历是值按照左节点->右节点->根节点的顺序的遍历。

数据范围：二叉树的节点数量满足 $1 \le n \le 100 \$ ，二叉树节点的值满足 $1 \le val \le 100 \$ ，树的各节点的值各不相同

样例图

示例1

输入

{1,#,2,3}

输出

[3,2,1]

说明

如题面图

示例2

输入

{1}

输出

[1]

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Python3

爱上咖啡

class Solution:

def postorderTraversal(self , root: TreeNode) -> List[int]:

# write code here

if root != None:

return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val]

return []

发表于 2025-07-11 17:36:37 回复(0)

Python3

Adam_Sun

非递归Python

class Solution:
    def postorderTraversal(self , root: TreeNode) -> List[int]:
        # write code here
        cur = root
        res, stack = [], []
        while cur&nbs***bsp;stack:
            if cur:
                stack.append(cur)
                res.append(cur.val)
                cur = cur.right
            else:
                cur = stack.pop()
                cur = cur.left
        return res[::-1]

发表于 2024-11-18 19:41:21 回复(0)

Python3

pzq

class Solution:
    res = []
    def postorderTraversal(self , root: TreeNode) -> List[int]:
        # 终止条件
        if root is None:
            return
        # 查找左节点
        self.postorderTraversal(root.left)
        # 查找右节点
        self.postorderTraversal(root.right)
        # 添加当前节点的值
        self.res.append(root.val)
        return self.res

发表于 2023-06-07 22:15:18 回复(0)

Python3

paradoxjun

Python3:非递归版

class Solution:
    def postorderTraversal(self , root: TreeNode) -> List[int]:
        # write code here
        if not root:
            return None
        
        stack = [(root, True)]
        ans = []

        while stack:
            node, flag = stack.pop()

            if (node.left&nbs***bsp;node.right) and flag:
                stack.append((node, False))
                if node.right:
                    stack.append((node.right, True))
                if node.left:
                    stack.append((node.left, True))

            else:
                ans.append(node.val)

        return ans

发表于 2022-10-03 15:34:32 回复(0)

Python3

StevenWqq

class Solution:
    def postorderTraversal(self , root: TreeNode) -> List[int]:
        # write code here
        res = []
        
        def postorder(root):
            if not root:
                return
            if root.left:
                postorder(root.left)
            if root.right:
                postorder(root.right)
            res.append(root.val) 
            return
            
        postorder(root)
        return res

发表于 2022-06-01 11:28:18 回复(0)