python - 考虑空节点,找到二叉树的两个节点之间的水平距离?
问题描述
我有二叉树,其中每个节点都拥有唯一的整数。我想找到位于同一水平面上的两个节点之间的水平距离。有些节点可能没有子节点或子子树,但要计算距离,我们还需要考虑那些空节点。就像在附加的二叉树中,距离(7, 1)=3 和距离(9, 4)=6。为此,我尝试了以下步骤:
- 将现有树转换为完整的二叉树。向不存在子子树或节点的节点添加空节点以满足完整的二叉树标准。
- 使用广度优先搜索算法遍历树并将遍历存储在字典中作为级别。
- 获取用户输入值,例如 level、first_node、second_node,并且在树中节点的所有验证之后给出它们之间的距离。
通过执行上述步骤,我得到了解决方案,但它需要O(N^2)的时间复杂度。使二叉树到完整二叉树需要O(N^2)以及使用 BFS 遍历需要O(N^2 ) 时间复杂度。
有没有其他方法可以解决这个问题,只需要遍历而不是完整的二叉树转换过程?
我的代码实现
from pprint import pprint
class Node:
def __init__(self, data):
self.data = data
self.right = None
self.left = None
@property
def maxDepth(self): # get the height of tree
depth = 0
if self.left: depth = self.left.maxDepth + 1
if self.right: depth = max(depth, self.left.maxDepth + 1)
return depth
def expandToDepth(self, depth=None): # full binary tree conversion method
if depth is None: depth = self.maxDepth
if not depth: return
if not self.left: self.left = Node(None)
if not self.right: self.right = Node(None)
self.left.expandToDepth(depth - 1)
self.right.expandToDepth(depth - 1)
d = {}
def traverse_dfs(root): # traverse the whole tree with BFS algo
h = root.maxDepth + 1
for i in range(1, h + 1):
level_traverse(root, i, i)
def level_traverse(root, level, original_level): # traverse the nodes at particular level
if root is None:
return
if level == 1:
if d.get(original_level):
d[original_level].append(root.data)
else:
d[original_level] = [root.data]
elif level > 1:
level_traverse(root.left, level - 1, original_level)
level_traverse(root.right, level - 1, original_level)
root = Node(5)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(7)
root.left.left.left = Node(9)
root.right.right = Node(1)
root.right.right.right = Node(6)
root.right.right.left = Node(4)
root.expandToDepth() # convert normal tree to full binary tree
traverse_dfs(root) # BFS traversal and stor the level wise traversal in dictionary d.
pprint(d)
level = int(input("Enter level: "))
first_node, second_node = map(int, input("Enter two nodes separated with space: ").split())
print("Getting horizontal distance between given nodes lies on the same level")
if first_node is None or second_node is None:
print("None type nodes are invalid")
exit()
if d.get(level):
if first_node in d[level] and second_node in d[level]:
distance = abs(d[level].index(first_node) - d[level].index(second_node))
print(distance)
else:
print("Distance invalid")
else:
print("Invalid level")
输出:
{1: [5],
2: [2, 3],
3: [7, None, None, 1],
4: [9, None, None, None, None, None, 4, 6]}
Enter level: 3
Enter two nodes separated with space: 7 1
Getting horizontal distance between given nodes lies on the same level
3
解决方案
实际上,添加缺失的节点是低效的。你可以在没有这些的情况下得出这个距离。想象一下两个选定节点的最低共同祖先,以及从那里到两个节点的路径如何提供有关可能存在的节点的线索。
例如,对于输入 9 和 4,共同祖先是根。从根到第一个节点的路径是 LLL(左-左-左)。另一条路径是 RRL。
现在让我们玩第一条路径。想象一下它是 LLR 而不是 LLL:这会使距离缩短 1。或者想象它是 LRL 而不是 LLL:这会使距离缩短 2。事实上,您会注意到这种单一路径的变化,会产生影响到距离是 2 的幂。幂是您与节点向上的距离。
所以,...您可以将这些路径创建为二进制数。在示例中:000 和 110。现在将它们作为二进制表示相减:你得到 6。这确实是距离。
所以你的代码可能是:
class Node:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def dfs(root, d={}, path=""):
if root:
d[root.data] = path
dfs(root.left, d, path+"0")
dfs(root.right, d, path+"1")
return d
root = Node(5)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(7)
root.left.left.left = Node(9)
root.right.right = Node(1)
root.right.right.right = Node(6)
root.right.right.left = Node(4)
# create a dictionary of <nodevalue, path>
d = dfs(root)
val1, val2 = map(int, input("Enter two nodes separated with space: ").split())
# convert the numbers to the corresponding paths:
node1 = d.get(val1, None)
node2 = d.get(val2, None)
# check whether these nodes actually exist
if node1 is None or node2 is None:
print("At least one value is invalid or not found")
exit()
# If the paths have different lengths, the nodes are not on the same level
if len(node1) != len(node2):
print("Nodes are not on the same level")
exit()
# Use the magic of binary numbers:
dist = abs(int(node1, 2) - int(node2, 2))
print(dist)
推荐阅读
- c# - 如何区分具有相似参数的 2 个端点?
- c# - 让 CefSharp 浏览器显示在 Window.Content 中
- android - 更新 Kotlin 版本后出现 Kapt 错误:java.lang.NoSuchFieldError: CONTENT_ROOTS
- java - 如何使用for循环循环二维数组?
- php - Laravel 5 日程安排问题 - php artisan schedule:run 有效,但实际日程安排无效
- javascript - expressJs 中的调试错误
- apache-spark - 使用 Spark 连接到 Greenplum 以读取数据时要使用的 jar 和驱动程序类是什么?
- sapui5 - 表的 getItems() 方法最多返回 20 行
- java - 如何以特定顺序关闭演员并能够在死前发送消息?
- amazon-web-services - Cloudformation 是否支持在 API Gateway 中使用代理集成选项?