n
l. r
n → l → r
recursivePreorder(_ node: Node) {
if node is nil {
return
}
print(node)
recursivePreorder(node.left)
recursivePreorder(node.right)
}
func iterativePreorder(_ node: Node) {
if node is nil {
return
}
var stack: [Int] = [node]
while !stack.isEmpty {
let pop_node = stack.removeLast()
print(pop_node.val)
if let r = pop_node.right {
stack.append(r)
}
if let l = pop_node.left {
stack.append(l)
}
}
}
l→ n→ r
recursiveInorder(_ node: Node) {
if node is nil {
return
}
recursiveInorder(node.left)
print(node)
recursiveInorder(node.right)
}
func iterativeInorder(_ node: Node) {
if node is nil {
return
}
var stack: [Int] = [node]
var curNode = node
while true {
if node != nil {
st.append(curNode)
curNode = curNode.left
}
else if !stack.isEmpty {
curNode = stack.pop()
print(curNode.val)
curNode = curNode.right
}
else {
break
}
}
}
l → r → n
recursivePostorder(_ node: Node) {
if node is nil {
return
}
recursivePostorder(node.left)
recursivePostorder(node.right)
print(node)
}
def iterativePostorder(node):
stack = []
last_visit_node = None
crnt_node = node
while True:
if crnt_node is not None:
stack.append(crnt_node)
crnt_node = crnt_node.left
elif 0<len(stack):
peek_node = stack[-1]
if peek_node.right and last_visit_node != peek_node.right:
crnt_node = peek_node.right
else:
print(peek_node.val, end=' ')
last_visit_node = stack.pop()
else:
break