class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def build_tree(n):
nodes = [TreeNode(i) for i in range(n)]
for i in range(n):
l = 2*i + 1
r = 2*i + 2
if l < n:
nodes[i].left = nodes[l]
if r < n:
nodes[i].right = nodes[r]
if r == n:
break
return nodes[0]
def level(root):
res = []
queue = [root]
while queue:
cur = queue.pop(0)
res.append(cur.val)
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
return res
def level2(root):
res = []
l1 = [root]
l2 = []
while l1:
cur = []
for node in l1:
cur.append(node.val)
if node.left:
l2.append(node.left)
if node.right:
l2.append(node.right)
l1, l2 = l2, []
res.append(cur)
return res
def preorder2(root):
if not root:
return
res = []
def helper(root):
nonlocal res
if not root:
return
res.append(root.val)
helper(root.left)
helper(root.right)
helper(root)
return res
def preorder(root):
if not root:
return []
stack = [root]
res = []
while stack:
cur = stack.pop()
res.append(cur.val)
if cur.right:
stack.append(cur.right)
if cur.left:
stack.append(cur.left)
return res
def inorder(root):
res = []
stack = []
cur = root
while stack or cur:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
res.append(cur.val)
cur = cur.right
return res
def postorder(root):
if not root:
return []
res = []
stack = [root]
while stack:
cur = stack.pop()
res.append(cur.val)
if cur.left:
stack.append(cur.left)
if cur.right:
stack.append(cur.right)
return res[::-1]
if __name__ == '__main__':
n = 7
root = build_tree(n)
print("层次遍历：", level(root))
print("层次遍历2：", level2(root))
print("前序遍历（非递归）：", preorder(root))
print("中序遍历（非递归）：", inorder(root))
print("后序遍历（非递归）：", postorder(root))
输出：
层次遍历： [0, 1, 2, 3, 4, 5, 6]
层次遍历2： [[0], [1, 2], [3, 4, 5, 6]]
前序遍历（非递归）： [0, 1, 3, 4, 2, 5, 6]
中序遍历（非递归）： [3, 1, 4, 0, 5, 2, 6]
后序遍历（非递归）： [3, 4, 1, 5, 6, 2, 0]
| 
转播
