[二叉树的后序遍历](https://leetcode.cn/problems/binary-tree-postorder-traversal/description/) ## 题目描述 给定一个二叉树的根节点 root，返回它的后序遍历结果。 后序遍历的定义：遍历左子树 → 遍历右子树 → 访问根节点 **示例** ```text 输入：root = [1,null,2,3] 输出：[3,2,1] 1 \ 2 / 3 ``` ```text 1 / \ 2 3 / \ \ 4 5 6 后序遍历顺序：4 → 5 → 2 → 6 → 3 → 1 ``` ```text 输入：root = [] 输出：[] ``` ## 解题思路 核心思想是：先递归地访问左子树，然后递归地访问右子树，最后访问当前节点。 **关注遍历执行的顺序: `左右根`** ```python # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]: values = [] def dfs( root_ ): if not root_: return dfs( root_.left ) dfs( root_.right ) values.append( root_.val ) dfs( root ) return values ``` **时间复杂度: `O(n)`** **空间复杂度: `O(h)`** n = 节点总数 h = 树的高度 ( 最坏情况`O(n)` 最好情况`O(log n)` )