python-3.x - python中二叉树的顶视图
问题描述
我正在尝试解决geeksforgeeks.com 上二叉树问题的俯视图
下面给出的是二叉树。任务是打印二叉树的顶视图。二叉树的顶视图是从顶部查看树时可见的节点集。对于下面给出的树
1 / \ 2 3 / \ / \ 4 5 6 7
俯视图为:4 2 1 3 7
注意:将节点从最左边的节点返回到最右边的节点。
有人能告诉我我的代码哪里错了吗?它适用于我尝试过的大多数案例,而对于一个太长而无法试运行的案例则失败了。
class Solution:
#Function to return a list of nodes visible from the top view
#from left to right in Binary Tree.
def topView(self,root):
left_ans = []
def left_view(root,level) :
if not root : return
if level > len(left_ans) : left_ans.append(root.data)
left_view(root.left,level+1)
left_view(root.right,level-1)
right_ans = []
def right_view(root,level) :
if not root: return
if level > len(right_ans) : right_ans.append(root.data)
right_view(root.right,level+1)
right_view(root.left,level-1)
left_view(root,level = 1)
right_view(root,level =1)
return left_ans[::-1]+right_ans[1:]
失败的树:
__________________23______________________
/ \
__17__ _________________65__________________
/ \ / \
__9__ 19 ______38_______ __69__
/ \ / \ / \ / \
7 10 18 21 37 __________43__________ 67 74
/ \ \ / \ / / \ / \ /
1 8 14 20 22 33 39 _______53_______ 66 68 70
\ / \ / / \ / \ \
4 13 16 __29_ 35 40 51 _62_ 71
/ \ / / / \ / \ \ / \ / \ \
3 5 11 15 27 32 34 36 41 45 52 __58__ 63 72
/ \ \ / \ / \ / \ / \ \ \
2 6 12 24 28 30 42 44 47 57 61 64 73
\ \ / \ / /
26 31 46 49 55 60
/ / \ / \ /
25 48 50 54 56 59
预期输出:
2 1 7 9 17 23 65 69 74 63 64
我的代码输出(错误):
2 1 7 9 17 23 65 69 74 72 73
解决方案
您的算法假定首先访问最高节点,但情况并非总是如此。这是一个最小的例子:
7
/ \
1 11
\ /
2 (10)
/ \
9 6
/ /
8 5
/
4
/
3
请注意,从根部弹出的两个分支向下交叉两层(11 的左孩子是 10,而 1 的右孩子是 2)。由于您首先访问左子树,因此您将注册 3 从顶部可见。当您稍后遍历另一条路径时,这不会得到更新。
一种解决方案是保持在哪个深度找到了节点。level
如果稍后,在相同的垂直偏移(
第二个问题是挑战提到解决方案应该“将节点从最左边的节点返回到最右边的节点”。. 这是一个有点模棱两可的说法,但它似乎意味着当两个节点处于相同的高度,并且处于相同的垂直偏移时,应该优先考虑通过左先遍历找到的节点。但是在right_view
您使用相反的顺序:只需更改递归调用的顺序。
depth
这是使用该概念和固定递归调用顺序更新的函数:
def topView(self,root):
left_ans = []
left_depth = []
def left_view(root,level,depth) :
if not root:
return
if level >= 0:
if level >= len(left_ans):
left_ans.append(root.data)
left_depth.append(depth)
elif depth < left_depth[level]:
left_ans[level] = root.data
left_depth[level] = depth
left_view(root.left,level+1,depth+1)
left_view(root.right,level-1,depth+1)
right_ans = []
right_depth = []
def right_view(root,level,depth):
if not root:
return
if level >= 0:
if level >= len(right_ans):
right_ans.append(root.data)
right_depth.append(depth)
elif depth < right_depth[level]:
right_ans[level] = root.data
right_depth[level] = depth
right_view(root.left,level-1,depth+1)
right_view(root.right,level+1,depth+1)
left_view(root,0,0)
right_view(root,0,0)
return left_ans[::-1]+right_ans[1:]
推荐阅读
- perl - 如何使用 Sed 或 Perl 根据字符串的第二列号以降序方式对给定的文本文件进行排序
- c - 如何添加两个数组以产生第三个?
- class - 我怎样才能让这个调度电话工作?
- javascript - e.preventDefault() 不适用于表单提交
- entity-framework-core - 使用原始 SQL 更改数据库内容会导致 EntityFramework 上下文不同步
- php - 如何从所有网站页面执行搜索?
- node.js - 在 node-expat@2.3.17 安装脚本失败 - 任何 NPM 安装都会发生
- javascript - 将类添加到包含 Dog 1 和其间行的表行
- c# - 为什么 RS485 返回发送的数据?
- ios - 圆形过渡,更改初始圆形大小