在一棵树中，查找两个节点值差值的绝对值的最大值

find_max_abs_diff_value.py

#!/usr/bin/env python
# coding: utf-8

"""
在一棵树中，查找两个节点值差值的绝对值的最大值
"""

__author__ = 'caoxudong'

from datastructure.common_datastructure import node

def breadth_first_search_output_tree(root=node.Node()):
  """
  广度优先遍历整个树，将其整个输出到另一个列表中
  """
  if root:
    queue = []
    queue.append(root)
    while len(queue):
      temp_node = queue.pop(0)
      node_list.append(temp_node)
      if temp_node.children and (len(temp_node.children) > 0):
        for e in temp_node.children:
          queue.append(e)

def fetch_result(node_list):
  if node_list == None or len(node_list) <= 2:
    return None
  else:
    min_node = node_list.pop(0)
    max_node = node_list.pop(0)
    if min_node.data > max_node.data:
      temp = max_node
      max_node = min_node
      min_node = temp
    while len(node_list) > 0:
      temp = node_list.pop()
      if temp.data > max_node.data:
        max_node = temp
      elif temp.data < min_node.data:
        min_node = temp
    return max_node.data - min_node.data

if __name__ == "__main__":
  """
  组装数据，生成一棵树
  """
  root = node.Node()
  node1 = node.Node()
  node2 = node.Node()
  node3 = node.Node()
  node4 = node.Node()
  node5 = node.Node()
  node6 = node.Node()
  node7 = node.Node()
  node8 = node.Node()
  root.children = [node1, node2]
  node1.children = [node3]
  node2.children = [node4]
  node3.children = [node5, node6, node7]
  node4.children = [node8]

  node_list = []
  # 广度优先遍历这棵树，将其所有节点都输出到一个列表中
  breadth_first_search_output_tree(root)
  # 输出结果
  print(fetch_result(node_list))