二叉树遍历

二叉树节点的定义

# simple版本，自己常用
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
# leetcode版本
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

构建二叉树

def create_binary_tree(input_list=[]):
    if input_list is None or len(input_list)==0:
        return None
    data = input_list.pop(0)
    if data is None:
        return None
    node = TreeNode(data)
    node.left = create_binary_tree(input_list)
    node.right = create_binary_tree(input_list)
    return node

深度优先遍历

144. 二叉树的前序遍历
94. 二叉树的中序遍历
145. 二叉树的后序遍历

# 前序遍历
def preorder(root):
    if root is None:
        return 
    print(root.val)        # 根
    preorder(root.left)   # 左
    preorder(root.right)  # 右
    return root
# 中序遍历
def inorder(root):
    if root is None:
        return 
    inorder(root.left)   # 左
    print(root.val)         # 根
    inorder(root.right)  # 右
    return root
# 后序遍历
def postorder(root):
    if root is None:
        return 
    postorder(root.left)   # 左
    postorder(root.right)  # 右
    print(root.val)        # 根
    return root

广度优先遍历

102. 二叉树的层序遍历

# 层序遍历
from queue import Queue
def levelOrder(root):
    if not root:
        return []
    queue = Queue()
    queue.put(root)
    ans = []
    while not queue.empty():
        tmp = []
        n = queue.qsize()
        for _ in range(n):
            root = queue.get()
            tmp.append(root.val)
            if root.left:
                queue.put(root.left)
            if root.right:
                queue.put(root.right)
        ans.append(tmp)
    return ans

107. 二叉树的层序遍历 II

N叉树遍历

N叉树节点的定义

class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children

深度优先遍历

589. N 叉树的前序遍历
590. N 叉树的后序遍历

# 前序遍历
def preorder(root):
    if root is None:
        return 
    print(root.val)              # 父
    for node in root.children:  # 子
        preorder(node)
    return root
# 后序遍历
def postorder(root):
    if root is None:
        return 
    for node in root.children:  # 子
        postorder(node)
    print(root.val)              # 父
    return root

广度优先遍历

429. N 叉树的层序遍历

# 层序遍历
from queue import Queue
def levelOrder(root):
    if not root:
        return []
    queue = Queue()
    queue.put(root)
    ans = []
    while not queue.empty():
        tmp = []
        n = queue.qsize()
        for _ in range(n):
            root = queue.get()
            tmp.append(root.val)
            for node in root.children:
                queue.put(node)
        ans.append(tmp)
    return ans