49 lines
1.1 KiB
Python
49 lines
1.1 KiB
Python
#
|
|
# @lc app=leetcode.cn id=145 lang=python3
|
|
#
|
|
# [145] 二叉树的后序遍历
|
|
#
|
|
|
|
# @lc code=start
|
|
# 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
|
|
|
|
|
|
from typing import Optional, List
|
|
|
|
from utils import *
|
|
|
|
|
|
class Solution:
|
|
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
|
|
res = []
|
|
stack = []
|
|
if not root:
|
|
return []
|
|
stack.append(root)
|
|
while stack:
|
|
node = stack[-1]
|
|
if node:
|
|
stack.pop()
|
|
stack.append(node)
|
|
stack.append(None)
|
|
if node.right:
|
|
stack.append(node.right)
|
|
if node.left:
|
|
stack.append(node.left)
|
|
else:
|
|
stack.pop()
|
|
node = stack.pop()
|
|
res.append(node.val)
|
|
return res
|
|
|
|
|
|
s = Solution()
|
|
s.postorderTraversal(generate_tree([1, None, 2, 3]))
|
|
|
|
# @lc code=end
|