Algorithm to Check if a Binary Tree can be Constructed via Hash

  • 时间:2020-10-07 14:14:07
  • 分类:网络文摘
  • 阅读:108 次

Have the function TreeConstructor(strArr) take the array of strings stored in strArr, which will contain pairs of integers in the following format: (i1,i2), where i1 represents a child node in a tree and the second integer i2 signifies that it is the parent of i1. For example: if strArr is [“(1,2)”, “(2,4)”, “(7,2)”], then this forms the following tree:

    4
   / 
  2  
 / \
1   7

which you can see forms a proper binary tree. Your program should, in this case, return the string true because a valid binary tree can be formed. If a proper binary tree cannot be formed with the integer pairs, then return the string false. All of the integers within the tree will be unique, which means there can only be one node in the tree with the given integer value.

Examples
Input: [“(1,2)”, “(2,4)”, “(5,7)”, “(7,2)”, “(9,5)”]
Output: true

Input: [“(1,2)”, “(3,2)”, “(2,12)”, “(5,2)”]
Output: false

Tags
array binary treedata engineer Google Facebook

Tree Constructor Algorithms using Hash Table

A valid tree should have the following characteristics:

  • A node should have at most 1 parent – the root does not have parents.
  • A node should have at most 2 children.

So, we can use two hash tables to record the number of parents and children for each node and return False immediately when we found violations.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def TreeConstructor(strArr):
  parents = {}
  children = {}
  for s in strArr:
    a, b = map(int, s.replace('(', '').replace(')', '').split(','))
    if a in parents:
      return False
    else:
      parents[a] = True
    if b in children:
      children[b] += 1
      if children[b] > 2:
        return False
    else:
      children[b] = 1
  return True
def TreeConstructor(strArr):
  parents = {}
  children = {}
  for s in strArr:
    a, b = map(int, s.replace('(', '').replace(')', '').split(','))
    if a in parents:
      return False
    else:
      parents[a] = True
    if b in children:
      children[b] += 1
      if children[b] > 2:
        return False
    else:
      children[b] = 1
  return True

The space complexity is O(N) and the time complexity is also O(N).

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
数学题:玉龙粮食加工厂生产一批面粉  数学题:从甲地到乙地的公路,只有上坡路和下坡路  数学题:求MN的长是多少  数学题:小红上学时坐车,回家步行  数学题:某班在植树活动中  数学题:三只猴子吃篮子里的桃子  数学题-实际比计划增加25%  甲植树的棵数是另外两人的二分之一  甲容器水深比乙容器水深低6厘米  第一次剪下2/5,又接上18米 
评论列表
添加评论