如何修改Python代码实现二叉树后序遍历

问题定位 #

现有代码的遍历函数func2为前序遍历实现，执行顺序为「打印当前节点→遍历左子树→遍历右子树」，因此输出前序序列4 2 1 3 6 5 7，不符合后序遍历要求。
代码中func1为平衡二叉树构造函数，逻辑无问题，不需要修改。

后序遍历逻辑 #

二叉树后序遍历的访问顺序严格遵循：

• 优先遍历当前节点的左子树
• 左子树遍历完成后遍历当前节点的右子树
• 左右子树全部遍历完成后，才访问当前节点的值

修改方式 #

仅需调整func2函数内的语句顺序，将节点值打印逻辑移动到左右子树递归调用的末尾即可。
修改后的完整代码：

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
    
def func1(nums):
    if not nums:
        return None
    mid_val = len(nums)//2
    node = TreeNode(nums[mid_val])
    node.left = func1(nums[:mid_val])
    node.right = func1(nums[mid_val+1:])
    return node

def func2(node): 
    if not node: 
        return      
    func2(node.left) 
    func2(node.right)
    print(node.val)

result = func1([1, 2, 3, 4, 5, 6, 7])
func2(result)

结果验证 #

修改后代码运行输出的后序遍历序列为1 3 2 5 7 6 4，与构造出的平衡二叉树后序遍历结果完全一致。

内容的提问来源于stack exchange，提问作者turtleee