（一）完成二叉树二叉链表结构的定义 （二）实现二叉链表的创建，先序、中序和后序遍历算法的实现。 （三）实现二叉树求结点个数，求高度，求叶子结点数、交换二叉树左右子树的算法。

一、二叉树二叉链表结构的定义：

class Node:
    def __init__(self, value):
        self.val = value
        self.left = None
        self.right = None

二、二叉链表的创建，先序、中序和后序遍历算法的实现：

class BinaryTree:
    def __init__(self):
        self.root = None

    def create_tree(self, values):
        self.root = self._create_tree_helper(values, 0)

    def _create_tree_helper(self, values, index):
        if index >= len(values):
            return None

        node = Node(values[index])
        node.left = self._create_tree_helper(values, 2 * index + 1)
        node.right = self._create_tree_helper(values, 2 * index + 2)

        return node

    def preorder_traversal(self):
        res = []

        def dfs(node):
            if not node:
                return

            res.append(node.val)
            dfs(node.left)
            dfs(node.right)

        dfs(self.root)
        return res

    def inorder_traversal(self):
        res = []

        def dfs(node):
            if not node:
                return

            dfs(node.left)
            res.append(node.val)
            dfs(node.right)

        dfs(self.root)
        return res

    def postorder_traversal(self):
        res = []

        def dfs(node):
            if not node:
                return

            dfs(node.left)
            dfs(node.right)
            res.append(node.val)

        dfs(self.root)
        return res

三、二叉树求结点个数，求高度，求叶子结点数、交换二叉树左右子树的算法：

class BinaryTree:
    def __init__(self):
        self.root = None

    def create_tree(self, values):
        self.root = self._create_tree_helper(values, 0)

    def _create_tree_helper(self, values, index):
        if index >= len(values):
            return None

        node = Node(values[index])
        node.left = self._create_tree_helper(values, 2 * index + 1)
        node.right = self._create_tree_helper(values, 2 * index + 2)

        return node

    def count_nodes(self):
        count = 0

        def dfs(node):
            nonlocal count

            if not node:
                return

            count += 1
            dfs(node.left)
            dfs(node.right)

        dfs(self.root)
        return count

    def get_height(self):
        def dfs(node):
            if not node:
                return 0

            left_height = dfs(node.left)
            right_height = dfs(node.right)

            return max(left_height, right_height) + 1

        return dfs(self.root)

    def count_leaves(self):
        count = 0

        def dfs(node):
            nonlocal count

            if not node:
                return

            if not node.left and not node.right:
                count += 1

            dfs(node.left)
            dfs(node.right)

        dfs(self.root)
        return count

    def invert(self):
        def dfs(node):
            if not node:
                return

            node.left, node.right = node.right, node.left
            dfs(node.left)
            dfs(node.right)

        dfs(self.root)