在二叉树中打印所有可能的路径 [英] Print all possible paths in binary tree
问题描述
我正在尝试在二叉树中打印所有可能的路径.我能够打印所有从根到叶的路径,但无法弄清楚如何添加从叶到叶的路径.(我正在使用从根到叶的预遍历).因此,基本上:
I'm trying to print all possible paths in a binary tree. I am able to print all root to leaf paths, but cannot figure out how to add leaf-to-leaf paths.(i'm using preorder traversal for root to leaf). So, basically:
如果我的树是
6
/ \
4 0
/ \ \
1 3 1
如果要在代码中打印所有路径,则:
If want to the code to print all the paths:
6,4,1
6,4,3
6,0,1
1,4,6,0,1
3,4,6,0,1
1,4,3
4,6,0
4,6,0,1
etc.
有人可以帮我解决这个二叉树吗?非常感谢您的帮助,因为我是这个社会和Python/Java的新手.
Can anyone please help me with this binary tree? I would really appreciate your help, as I'm new to this society and to Python/Java.
谢谢
推荐答案
树的一个显着特性是,对于节点(x,y)
的每种组合,都存在唯一的非重复路径从 x
到 y
.特别地,可以通过找到 x
和 y
的第一个公共祖先 z
并采用路径 x来找到此路径->z + z->y
.
One notable property of trees is that for every combination of node (x, y)
, there exist a unique non-repeating path from x
to y
. In particular, this path can be found by finding the first common ancestor z
of x
and y
and by taking the path x -> z + z -> y
.
因此查找所有路径的算法可能如下所示
Thus an algorithm to find all path could look like this
for each pair of distinct nodes x, y in the tree:
find all common ancestors of x and y
let z be the lowest common acestor in the tree
let p be the path from x to z
append the path from z to y to p, excluding the duplicate z
print p
这是一种面向对象的方法,它实现了完成上述任务所需的方法.
Here is an object-oriented approach that implements the needed method to accomplish the above.
class Tree:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
self.parent = None
if left is not None:
left.parent = self
if right is not None:
right.parent = self
def __iter__(self):
"""Return a left-to-right iterator on the tree"""
if self.left:
yield from iter(self.left)
yield self
if self.right:
yield from iter(self.right)
def __repr__(self):
return str(self.value)
def get_ancestors(self):
"""Return a list of all ancestors including itself"""
ancestors = {self}
parent = self.parent
while parent:
ancestors.add(parent)
parent = parent.parent
return ancestors
def get_path_to_ancestor(self, ancestor):
"""
Return the path from self to ancestor as a list
output format: [self, ..., ancestor]
"""
path = []
parent = self
try:
while True:
path.append(parent)
if parent is ancestor:
break
else:
parent = parent.parent
except AttributeError:
return None
return path
def get_path_to(self, other):
"""
Return the path from self to other as a list
output format: [self, ..., first common acestor, ..., other]
"""
common_ancestors = self.get_ancestors() & other.get_ancestors()
first_common_ancestor = {
a for a in common_ancestors
if a.left not in common_ancestors and a.right not in common_ancestors
}.pop()
return self.get_path_to_ancestor(first_common_ancestor)\
+ list(reversed(other.get_path_to_ancestor(first_common_ancestor)))[1:]
这是将其应用于您作为示例提供的树的方法.
Here is how it applies to the tree you provided as example.
tree = Tree(
6,
Tree(4,
Tree(1),
Tree(3)),
Tree(0,
Tree(1)))
nodes = list(tree)
for i in range(len(nodes)):
for j in range(i + 1, len(nodes)):
print([t for t in nodes[i].get_path_to(nodes[j])])
这里是所有打印的路径.
Here are all paths that get printed.
[1, 4]
[1, 4, 3]
[1, 4, 6]
[1, 4, 6, 0, 1]
[1, 4, 6, 0]
[4, 3]
[4, 6]
[4, 6, 0, 1]
[4, 6, 0]
[3, 4, 6]
[3, 4, 6, 0, 1]
[3, 4, 6, 0]
[6, 0, 1]
[6, 0]
[1, 0]
这篇关于在二叉树中打印所有可能的路径的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!