defpre_order(root):""" 前序: 根 左 右 stack: 入栈顺序: 右 左 出栈顺序: 左 右 """ifnotroot:return[]stack=[]res=[]stack.append(root)whilestack:root=stack.pop()res.append(root.val)ifroot.right:stack.append(root.right)ifroot.left:stack.append(root.left)returnresdefin_order(root):""" 中序: 左 根 右 stack root 不断压入左 没有左了 弹出一个根 看有没右节点 接着不断压入右节点的左 """ifnotroot:return[]stack=[]res=[]whilestackorroot:ifroot:stack.append(root)root=root.leftelse:root=stack.pop()res.append(root.val)root=root.rightdefpost_order(root):""" 后序: 左 右 根 stack root stack: 压一个根 并 将其添加到res的队首 且 不断压入右 出一个 看左 """ifnotroot:return[]stack=[]res=[]whilestackorroot:ifroot:stack.append(root)res.insert(0,root.val)root=root.rightelse:root=stack.pop()root=root.leftreturnresdefpost_order(root):ifnotroot:return[]stack=[]res=[]stack.append(root)whilestack:root=stack.pop()ifroot.left:stack.append(root.left)ifroot.right:stack.append(root.right)res.insert(0,root.val)returnres
