阿坝州网站建设公司

剑指offer：二叉树中和为某一值的路径-创新互联

题目描述
输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

创新互联2013年开创至今，先为镇海等服务建站，镇海等地企业，进行企业商务咨询服务。为镇海企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    """
    根据题目定义，一个路径总是从根节点开始的，而搜索路径本质上又和树的遍历有关，那么我们可以思考常
    用的树的遍历中哪种遍历方法可能有效，在这里答案就是先序遍历，因为先序遍历也是从根节点开始的。
    由于题目要求搜索所有可能的路径，一个路径在一层里面只经过一个节点，那么就是深度优先搜索DFS。

    具体到路径的定义，需要从根节点到叶节点，因此每遍历到一个节点的时候，如果这个节点是叶节点，那么
    我们就应该判断当前的路径是否符合要求，而如果这个节点不是叶节点，那么就选择一个子节点继续遍历。
    当一个节点的所有子节点都已经访问完毕之后，由于递归的特性会自动返回到其父节点，因此我们需要手动
    从路径中删除这个节点
    """
    def FindPath(self, root, expectNumber):
        def helper(cur_root, path):
            # 遍历到一个节点的时候先将其加入路径中
            path.append(cur_root.val)
            # 如果这个节点是叶节点，那么判断当前路径是否符合要求
            if not cur_root.left and not cur_root.right:
                if sum(path) == expectNumber:
                    # 这里注意不能res.append(path)，因为path只是一个id，绑定了内存中的
                    # 一个列表，而我们后面还会修改这个列表，因此需要将当前路径的一个拷贝加到
                    # 返回结果当中
                    res.append(path[:])

            # 如果当前节点不是叶节点，那么访问其子节点
            if cur_root.left:
                helper(cur_root.left, path)
            if cur_root.right:
                helper(cur_root.right, path)

            # 在访问完这个节点的所有子节点之后会返回到其父节点中，
            # 在返回之前应该在路径中删除这个节点
            path.pop(-1)

        if not root:
            return []

        res = []
        helper(root, [])
        return res

def main():
    root = TreeNode(10)
    root.left = TreeNode(5)
    root.right = TreeNode(12)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(7)

    solution = Solution()
    print(solution.FindPath(root, 22))

if __name__ == '__main__':
    main()

另外有需要云服务器可以了解下创新互联cdcxhl.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。


文章名称：剑指offer：二叉树中和为某一值的路径-创新互联
网站URL：http://azwzsj.com/article/hgejp.html

其他资讯