剑指offer:二叉树中和为某一值的路径

发布时间:2020-07-18 21:55:24 作者:Jayce_SYSU
来源:网络 阅读:371

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

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()
推荐阅读:
  1. thinkphp判断数组中的某一项是否为空值
  2. 剑指offer:序列化二叉树

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

遍历 深度优先dfs

上一篇:good ways to define a JavaScript class

下一篇:apache和php动态加载模块

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》