二叉树（2）----路径

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

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

采用两个递归思路：时间复杂度O（N²），空间复杂度O（1）

代码：

class  TreeNode:
    def __init__(self,value):
        self.val = value
        self.left = None
        self.right = None
#主要思路：
class Solution:
    def pathSum(self,root,sum):
        self.res = 0
        #步骤1，遍历所有节点，每个节点都经历步骤2
        def step1(root,sum):
            if root:
                step2(root,0,0,sum)
                if root.left:
                    step1(root.left,sum)
                if root.right:
                    step1(root.right,sum)
        #步骤2，遍历其所有孩子节点，将满足条件的结果输出
        def step2(root,a,b,sum):
            if root:
                a += root.val
                b += 1
                if a == sum:
                    self.res = max(self.res,b)
                if root.left:
                    step2(root.left,a,b,sum)
                if root.right:
                    step2(root.right,a,b,sum)
                
        step1(root,sum)
        return self.res
root = TreeNode(-3)
root.left = TreeNode(3)
root.right = TreeNode(-9)
root.left.left = TreeNode(1)
root.left.right = TreeNode(0)
root.right.left = TreeNode(2)
root.right.right = TreeNode(1)
root.left.right.left = TreeNode(1)
root.left.right.right = TreeNode(6)
sum = 6
a = Solution()
a.pathSum(root,sum)

采用哈希表（字典）的思路：时间复杂度O（N），空间复杂度O（h），h为树的高度，N为树节点的个数

参考【未排序数组中累加和为规定值的最长子数组长度】，arr【i……j】=s【j】-s【i】，字典存储s，key表示和s，value表示索引位置 i 。

来自https://blog.csdn.net/qq_34342154/article/details/76409019

1、采用字典存储累加和，key表示某个累加和，value表示累加和出现的最早层数。

如：某个路径上的节点值为【1，2，3，-3，5】，则字典中的记录为【1：1，3：2，6：3，3：2，8：5】，由于value表示累加和出现的最早层数，则第二条记录和第四条记录相同，故字典的记录应该为【1：1，3：2，6：3，8：5】

2、在字典中添加（0，0）记录，表示累加和0不用任何节点就 可以得到。先序遍历二叉树，假设遍历到的当前位置为cur，层数为level，此时的累加和应为cur的父节点的累加和presum 加上 cur节点的值，即cursum = presum + cur.val。如果（presum + cur.val, level）这个记录已经存在于字典中，则不需要再次加入。之后，判断是否有以cur结尾的路径的累加和等于题目所给的指定值sum。只需要在字典中寻找是否有cursum - sum这个记录即可，如果存在这个记录的话，level - map[cursum - sum]就是满足条件的一个路径长度，使用全局变量更新路径的最大值。

3、注意，在遍历完二叉树的子树要返回cur的父节点是，需要将map中该节点的记录删去（如果之前插入的话），否则可能出现路径不是自顶向下的情况。【原因：假设当前节点左子树节点为2，右子树节点为1，当前节点为1，给定值K为4，则存在非自顶向下的情况】

def getMaxLength(root, K):
    def getLengthByPreOrder(root, K, preSum, level, length, map):
        if not root:
            return length
        curSum = preSum + int(root.val)
        if curSum not in map:
            map[curSum] = level
        if curSum-K in map:
            length = max(level - map.get(curSum-K), length)
        length = getLengthByPreOrder(root.left, K, curSum, level+1, length, map)
        length = getLengthByPreOrder(root.right, K, curSum, level+1, length, map)
        if level == map.get(curSum):
            map.pop(curSum)
        return length


    if not root:
        return
    map = {}
    map[0] = 0
    return getLengthByPreOrder(root, K, 0, 1, 0, map)