python 二叉树，先序回溯，层序队列，队列基础用法，二叉树深度

1.创建二叉树，先、中、后遍历

# 创建二叉树
class TreeNode():
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

    def __str__(self):
        return str(self.data)
# 例
A = TreeNode('A')
B = TreeNode('B')
C = TreeNode('C')
A.left = B
A.right = C
print('A.left:', A.right, '   A.right:', A.left)

def createTree():
    A, B, C, D, E, F, G, H, I = [TreeNode(x) for x in 'ABCDEFGHI']
    A.left = B
    A.right = C
    B.right = D
    C.left = E
    C.right = F
    E.left = G
    F.left = H
    F.right = I
    return A

# 遍历
def preOrder(node):
    # 先序遍历
    if not node:
        return
    print(node)
    preOrder(node.left)
    preOrder(node.right)

def inOrder(node):
    # 中序遍历
    if not node:
        return
    inOrder(node.left)
    print(node)
    inOrder(node.right)

def postOrder(node):
    # 后序遍历
    if not node:
        return
    postOrder(node.left)
    postOrder(node.right)
    print(node)

# 不使用递归
def preOrderIter(root):
    s = []
    node = root
    while True:
        while node:
            print(node)
            s.append(node)
            node = node.left
        if not s:
            break
        node = s.pop().right

root = createTree()
print('preOrder:')
preOrder(root)

print('preOrderIter:')
preOrderIter(root)

2.n个节点有多少种二叉树，递归

def count_tr1(n): 
    # root: 1
    # left: k   [0, n - 1]
    # right: n - 1 - k
    count = {0 : 1}
    s = count.get(n, 0)
    if s:
        return s
    for k in range(n):
        s += binary_tree.count_tr1(k) * binary_tree.count_tr1(n - 1 - k)
    count[n] = s
    return s

3.层序遍历

from collections import deque
import createtree


def leverOrder(root):
    q = deque([root])

    while q:
        node = q.popleft() # 从左端获取并移除节点
        print(node)

        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)

if __name__ == '__main__':
    root = createtree.createTree()
    leverOrder(root)

4.队列基础用法

# 导入
from collections import deque

# 创建
q = deque()

# 右段插入
q.append(element)

# 左端插入
q.appendleft(element)

# 右端删除并返回
 element = q.pop()

# 左端删除并返回
element = q.popleft()

# 清空队列
q.clear()

五，二叉树深度

# 二叉树的深度
# 思路一：找到当前节点左子树和右子树的深度，取大的一个并加1
def depth(node):
    while node:
        dl = depth(node.left)
        dr = depth(node.right)
        return max(dl, dr) + 1
    return 0

# 思路二：已经有层序遍历了，层序遍历的最后一个元素的层数不就是深度吗？所以层序遍历时记录深度即可
def depth2(root):
    q = deque([(root, 1)])  # 通过列表创建队列
    while q:
        node, d = q.popleft()  # 从左端获取并移除节点
        if node.left:
            q.append((node.left, d+1))
        if node.right:
            q.append((node.right, d+1))
    return d