题目：

Randomly generates a binary search tree whose number of nodes is determined by user input, with labels ranging between 0 and 999,999, displays it, and outputs the maximum difference between consecutive leaves.

题目大意：

随机产生一个二叉树，该二叉树是根据用户输入的随机数产生的。之后程序会展示该二叉树。求出该二叉树连续的两个叶子差的最大值。

输入输出示例：

输入输出示例

思路：

很明显这道题就是二叉树的前序遍历。在遍历二叉树的过程中如果找到某个结点，它的Right_Node.Value和Left_Node.Value都是None，那么该结点就是叶子结点。同时计算该叶子结点与上一个叶子结点之间的差，并和最初设置的最大值Max做一个比较并设置一个变量记录下该叶子结点的值。

这道题我前序遍历使用的是非递归形式。这里需要定义一个栈stack和树结点p，p一开始指向树的根节点，stack存储p经过的结点。p首先向左走，一旦找到满足叶子结点的结点的时候进行最大值判断。如果只是左结点为空，将它的右结点存储到栈中，将p指向的结点弹出栈并使得p指向刚刚加入到栈中的右结点。继续循环。循环的过程中p需要记录每一次走过的结点。循环的跳出条件是栈stack为空并且p指向空。

代码：

import sys
from random import seed, randrange
from binary_tree_adt import *
import queue

# Possibly define some functions

def max_diff_in_consecutive_leaves(tree):
    '''
    Find the maximum difference between leaves.
    :param tree:
    :return:
    '''
    if tree is None:
        return 0
    max = 0
    leave = 0
    flag = False
    q = queue.deque()
    p = tree
    while q.__len__() != 0 or (p is not None and p.value is not None):
        while p is not None and p.value is not None:
            if (p.left_node is None and p.right_node is None) or ((p.left_node is not None and p.left_node.value is None ) and (p.right_node is not None and p.right_node.value is None)):
                if flag:
                    if abs(p.value - leave) > max:
                        max = abs(p.value - leave)
                    leave = p.value
                else:
                    leave = p.value
                    flag = True
            q.append(p)
            p = p.left_node

        if q.__len__() != 0:
            p = q.pop()
            p = p.right_node

    return max

provided_input = input('Enter two integers, the second one being positive: ')
try:
    arg_for_seed, nb_of_nodes = provided_input.split()
except ValueError:
    print('Incorrect input, giving up.')
    sys.exit()
try:
    arg_for_seed, nb_of_nodes = int(arg_for_seed), int(nb_of_nodes)
    if nb_of_nodes < 0:
        raise ValueError
except ValueError:
    print('Incorrect input, giving up.')
    sys.exit()
seed(arg_for_seed)
tree = BinaryTree()
for _ in range(nb_of_nodes):
    datum = randrange(1000000)
    tree.insert_in_bst(datum)
print('Here is the tree that has been generated:')
tree.print_binary_tree()
print('The maximum difference between consecutive leaves is: ', end = '')
print(max_diff_in_consecutive_leaves(tree))