在二叉树中找到累加和为指定值的最长路径长度

在二叉树中找到累加和为指定值的最长路径长度

Description

给定一颗二叉树和一个整数 sum，求累加和为 sum 的最长路径长度。路径是指从某个节点往下，每次最多选择一个孩子节点或者不选所形成的节点链。

分析

题目的意思是：这道题在求路径和为sum的基础上加了一个限制条件，即路径必须最长。所以在找到符合条件的路径的时候，要判断路径的长度，这时可以利用字典来存储信息，字典存放的是根结点到当前节点的累加和和层数的映射。

字典首先添加{0:0}记录，表示累加和为0不用任何节点就可以得到。然后先序遍历二叉树，假设遍历到的当前位置是cur，层数为level，此时的累加和应为cur的父节点的累加和presum加上cur节点的值，即cursum = presum + cur.val。如果（presum + cur.val, level）这个记录已经存在于字典中，则不需要再次插入。接下来，判断是否有以cur结尾的路径的累加和等于题目所给的指定值sum。只需要在map中寻找是否有cursum - sum这个记录即可，如果存在这个记录的话 level - d[cursum - sum]就是满足条件的一个路径长度，使用全局变量更新路径的最大值。需要注意的是，在遍历完二叉树的子树要返回到cur的父节点是，需要将map中该节点的记录删去（如果之前插入的话），否则可能出现路径不是自顶向下的情况。

这道题出自左神写的程序员面试指南，思路还是比较新颖的，我学习一下思路。

代码

import collectionsclass TreeNode(): def __init__(self,val): self.val=val self.left=None self.right=Nonedef solve(root,K,preSum,level,l,d): if(root is None): return l curSum=preSum+root.val if(curSum not in d): d[curSum]=level # print(d) if(curSum-K in d): l=max(level-d[curSum-K],l) l=solve(root.left,K,curSum,level+1,l,d) l=solve(root.right,K,curSum,level+1,l,d) if(level==d[curSum]): d.pop(curSum) return ldef getMaxLength(root,K): d=collections.defaultdict(int) d[0]=0 return solve(root,K,0,1,0,d)if __name__ == "__main__": vals = [-3, 3, -9, 1, 0, 2, 1, 1, 6] nodes = [TreeNode(v) for v in vals] root = nodes[0] nodes[0].left, nodes[0].right = nodes[1], nodes[2] nodes[1].left, nodes[1].right = nodes[3], nodes[4] nodes[2].left, nodes[2].right = nodes[5], nodes[6] nodes[4].left, nodes[4].right = nodes[7], nodes[8] assert(getMaxLength(root, 6) == 4) assert(getMaxLength(root, -9) == 1) assert(getMaxLength(root, -10) == 3) assert(getMaxLength(root, -11) == 3) assert(getMaxLength(root, 4) == 3) assert(getMaxLength(root, 1) == 4) assert(getMaxLength(root, 3) == 2)

参考文献

​​ [编程题]在二叉树中找到累加和为指定值的最长路径长度​​​​二叉树中累加和为指定值的最长路径​​​​二叉树问题—在二叉树中找到累加和为指定值的最长路径长度​​​​在二叉树中找到累加和为指定值的最长路径长度​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。