題目：

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.

題目大意：

隨機(jī)產(chǎn)生一個二叉樹，該二叉樹是根據(jù)用戶輸入的隨機(jī)數(shù)產(chǎn)生的。之后程序會展示該二叉樹。求出該二叉樹連續(xù)的兩個葉子差的最大值。

輸入輸出示例：

輸入輸出示例

思路：

很明顯這道題就是二叉樹的前序遍歷。在遍歷二叉樹的過程中如果找到某個結(jié)點(diǎn)，它的Right_Node.Value和Left_Node.Value都是None，那么該結(jié)點(diǎn)就是葉子結(jié)點(diǎn)。同時計(jì)算該葉子結(jié)點(diǎn)與上一個葉子結(jié)點(diǎn)之間的差，并和最初設(shè)置的最大值Max做一個比較并設(shè)置一個變量記錄下該葉子結(jié)點(diǎn)的值。

這道題我前序遍歷使用的是非遞歸形式。這里需要定義一個棧stack和樹結(jié)點(diǎn)p，p一開始指向樹的根節(jié)點(diǎn)，stack存儲p經(jīng)過的結(jié)點(diǎn)。p首先向左走，一旦找到滿足葉子結(jié)點(diǎn)的結(jié)點(diǎn)的時候進(jìn)行最大值判斷。如果只是左結(jié)點(diǎn)為空，將它的右結(jié)點(diǎn)存儲到棧中，將p指向的結(jié)點(diǎn)彈出棧并使得p指向剛剛加入到棧中的右結(jié)點(diǎn)。繼續(xù)循環(huán)。循環(huán)的過程中p需要記錄每一次走過的結(jié)點(diǎn)。循環(huán)的跳出條件是棧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))