首页 > 试题广场 >

二叉树中和为某一值的路径(二)

[编程题]二叉树中和为某一值的路径(二)

热度指数：781778 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

输入一颗二叉树的根节点root和一个整数expectNumber，找出二叉树中结点值的和为expectNumber的所有路径。

1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点

2.叶子节点是指没有子节点的节点

3.路径只能从父节点到子节点，不能从子节点到父节点

4.总节点数目为n

如二叉树root为{10,5,12,4,7},expectNumber为22

则合法路径有[[10,5,7],[10,12]]

数据范围:

树中节点总数在范围 [0, 5000] 内

-1000 <= 节点值 <= 1000

-1000 <= expectNumber <= 1000

示例1

输入

{10,5,12,4,7},22

输出

[[10,5,7],[10,12]]

说明

返回[[10,12],[10,5,7]]也是对的

示例2

输入

{10,5,12,4,7},15

输出

[]

示例3

输入

{2,3},0

输出

[]

示例4

输入

{1,3,4},7

输出

[]

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Python

Dinochang

发表于 2022-04-08 16:59:55 回复(0)

Python

Quinn_5400

一.题意理解: 到叶子节点、和为目标值

二.树一般采用递归,基础单元处理逻辑梳理:因为从跟节点开始,所以采用先序遍历;对于一个节点遍历时记录序列和目标值变化,遍历完后进行还原

三.满足题意判断后不停止,遍历所有可能

# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def __init__(self):
self.rlist = []
self.tlist = []
# 返回二维列表，内部每个列表表示找到的路径
def FindPath(self, root, expectNumber):
# write code here
if not root:
return self.rlist
# 遍历该节点时进行路径记录和目标值变化
self.tlist.append(root.val)
expectNumber -= root.val
# 结果满足性判断
if expectNumber == 0 and not root.left and not root.right:
self.rlist.append(list(self.tlist))
# 递归完成左右子树的判断
self.FindPath(root.left, expectNumber)
self.FindPath(root.right, expectNumber)
# 如果该节点遍历完毕进行还原
expectNumber += root.val
self.tlist.pop()
return self.rlist

发表于 2021-04-27 14:39:05 回复(0)

Python

学习不能停下呀

import copy
# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def __init__(self):
        self.dry=[]#该列表用于保存结果
        self.temp=[]#该列表保存当前节点往上遍历过的值，即从根节点到其父节点
    def FindPath(self, root, expectNumber):
        # write code here
        self.findpath(root,expectNumber)
        return self.dry
    def findpath(self,root,expectNumber):#对于每一个节点，进行如下操作
        #该函数对每一个节点进行三部操作
        #用遍历完成题目要求
        if root:
            self.temp.append(root.val)
            if root.left:#如果有左子树，则对左子树递归
                self.findpath(root.left, expectNumber)
            if root.right:#如果该节点有右子树，则对右子树进行递归
                self.findpath(root.right, expectNumber)
            if sum(self.temp)==expectNumber and (root.left==None) and (root.right==None):
                #如果该节点为叶节点，则判断走过路径和是否满足要求
                    temp=copy.deepcopy(self.temp)
                    self.dry.append(temp)
                    self.temp.pop()#退出该节点的遍历前删除该节点在self.temp中的值
            else:
                    self.temp.pop()#退出该节点的遍历前删除该节点在self.temp中的值

发表于 2021-02-10 19:31:11 回复(0)

Python

120天

## 深度优先遍历，得到所有路劲+求和判断

class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
#import numpy as np
class Solution:

# 返回二维列表，内部每个列表表示找到的路径
def FindPath(self, root, expectNumber):
if root==None:
return []
path=[root.val]
all_path=[]
self.DFS(root, path, all_path)
res=[]
for one_path in all_path:
print(one_path)
if sum(one_path)==expectNumber:
res.append(one_path)
return res
def DFS(self,root,path,all_path):
if(not root.left) & (not root.right):
all_path.append(path)

if(root.left):
self.DFS(root.left, path+[root.left.val], all_path)
if (root.right):
self.DFS(root.right, path+[root.right.val], all_path)

return all_path

发表于 2021-01-10 12:01:58 回复(0)

Python

DDooo

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        # write code here
        paths = self.dfs(root)
        p_list = []
        for p in paths:
            if sum(p) == expectNumber:
                p_list.append(p)
        return p_list
        #return [p for p in paths if sum(p) == expectNumber]
            
    def dfs(self,root):
        if not root:
            return []
        if not root.left and not root.right:
            return [[root.val]]
        paths = [[root.val] + path for path in self.dfs(root.left)]+[[root.val]+ path for path in self.dfs(root.right)]
        return paths

注意，

return [p for p in paths if sum(p) == expectNumber]

的等价写法：

p_list = []
        for p in paths:
            if sum(p) == expectNumber:
                p_list.append(p)
        return p_list

发表于 2020-08-06 16:40:53 回复(0)

Python

sk8_wt

class Solution:

    def FindPath(self, root, expectNumber):
        self.result = []
        self.expect = expectNumber
        self.find(root,[])
        return self.result
    
    def find(self,proot,counter=[]):
        if not proot:
            return counter
        counter.append(proot.val)
        self.find(proot.left,counter)
        self.find(proot.right,counter)
        if proot.left == None and proot.right == None and sum(counter) == self.expect:
            self.result.append(counter[:])  
        return counter.remove(proot.val)

发表于 2020-06-26 22:12:58 回复(0)

Python

生下来就会跑

class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        # write code here
        if not root:return []
        self.result=[]
        self.find(root,expectNumber,[],0)
        return self.result
    def find(self,root,Number,path,sum):
        sum += root.val
        path.append(root.val)
        if not root.left and not root.right:
            if  sum == Number:
                self.result.append(path)
                return 
            else:
                return
        nextpath=path[:]
        if root.left:
            self.find(root.left,Number,nextpath,sum)
        nextpath=path[:]
        if root.right:
            self.find(root.right,Number,nextpath,sum)
        return

发表于 2020-06-22 23:16:05 回复(0)

Python

芝麻不加饼

class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        res=[]
        sub=[]
        self.ext(root, expectNumber,0,res,sub)
        return res
    def ext(self, root, expectNumber,partial,res,sub):
        if not root:
            return None
        sub.append(root.val)
        partial+=root.val
        if not root.left and not root.right:
            if partial == expectNumber:
                res.append(sub)
        self.ext(root.left, expectNumber,partial,res,sub[:])
        self.ext(root.right, expectNumber,partial,res,sub[:])

发表于 2020-05-31 13:13:51 回复(0)

Python

黑人球员

用例:{10,5,12,4,7},15
对应输出应该为:[]
你的输出为:[[10,5]]
这个用例的答案是不是不太对？

发表于 2020-05-18 12:48:33 回复(0)

Python

fregoco

class Solution:
    def __init__(self):
        self.valLst = []#存放单路径结点
        self.lst = []#存放所有路径
    def FindPath(self, root, expectNumber):
        if root == None:
            return []
        expectNumber = expectNumber-root.val
        self.valLst.append(root.val)
        self.FindPath(root.left, expectNumber)
        self.FindPath(root.right, expectNumber)
        if expectNumber == 0 and root.left == None and root.right == None:#在根节点满足条件则将路径加入列表
            self.lst.append([x for x in self.valLst])
        self.valLst.pop()
        return self.lst

self.lst.append([x for x in self.valLst])

python坑爹的深浅复制问题，如果将列表

self.valLst

直接放入列表

self.lst[self.valLst]

中时是浅复制，如果self.valLst改变，那么self.lst列表中的相应表项也会跟着改变，会出现意想不到的结果，只好用for表达式重新创建了一个新的列表加入self.lst

编辑于 2020-04-16 00:20:41 回复(0)

Python

canikissyou

class Solution:
    def getPaths(self,root,path,paths,expectNumber):
      if root:
        path.append(root)
        self.getPaths(root.left,path,paths,expectNumber)
        self.getPaths(root.right,path,paths,expectNumber)
        if not root.left and not root.right:#当访问到叶子节点时
          if sum([node.val for node in path])==expectNumber:
            paths.append([node.val for node in path])
        path.pop() #当左子树和右子树都访问过，出栈
      return paths
    def FindPath(self, root, expectNumber):
        return self.getPaths(root,[],[],expectNumber)

编辑于 2020-03-20 16:55:04 回复(0)

Python

accer

class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        (1493)# write code here
        if root == None:
            return []
        if (root.left == None) and (root.right == None) and (root.val == expectNumber):
            return [[expectNumber]]
        returnList = []
        pathList = [root.val]
        returnList=self.search(root.left, expectNumber, returnList, pathList)
        pathList = [root.val]
        returnList=self.search(root.right, expectNumber, returnList, pathList)
        return returnList
         
    def search(self, root, expectNumber, returnList, pathList):
        if root == None:    # Leaf Node
            if sum(pathList) == expectNumber:  (1771)# wanted path
                if len(returnList)  and len(returnList[0]) < len(pathList): # put it in order
                    returnList.insert(0, pathList)
                else:
                    returnList.append(list(pathList))
            return  returnList(1772)# no need to go on, exit   #####################################
        else:
            if sum(pathList) > expectNumber&nbs***bsp;(root.val + sum(pathList) > expectNumber): (1773)# not meet the requirment, exit
                pathList.pop()
                return returnList                       # (750)##############################
            pathList.append(root.val)(1774)# go on
            self.search(root.left, expectNumber, returnList, pathList)
            if root.right:
                if root.left != None:
                    pathList.pop()
                self.search(root.right, expectNumber, returnList, pathList)
        return  returnList

发表于 2020-03-08 00:58:07 回复(0)

Python

朝夕_

class Solution:
    def FindPath(self, root, expectNumber):
        ans = []
        def DFS(root, temp, sum_e):
            if not root:
                return []
            if not root.left and not root.right and sum_e - root.val == 0: 
                temp += [root.val]
                ans.append(temp)
            DFS(root.left, temp + [root.val], sum_e - root.val)
            DFS(root.right, temp + [root.val] , sum_e - root.val)
            return
        DFS(root, [], expectNumber)
        return ans

发表于 2020-03-02 21:25:19 回复(0)

Python

牛客447097232号

注意路径是根节点到叶子节点

# -*- coding:utf-8 -*-
"""
dfs遍历即可，注意路径是root到子节点，相对更简单
"""
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        self.ans = []
        if not root:
            return self.ans
        else:
            self.dfs(root, expectNumber, [])
            return self.ans

    def dfs(self,x,target,path):
        if not x:
            return None
        if x.val == target and not x.right and not x.left:
            self.ans.append(path+[x.val])
        else:
            self.dfs(x.left, target - x.val, path + [x.val])
            self.dfs(x.right, target - x.val, path + [x.val])



s = Solution()
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(12)
root.left.left = TreeNode(4)
root.left.right = TreeNode(7)
ans = s.FindPath(root,22)
print(ans)

编辑于 2020-02-28 16:58:22 回复(0)

Python

天山剑客

# -*- coding:utf-8 -*-
# 解题思路：二叉树递归实现前序遍历，用一个list保存路径上的值，遇到叶子节点求list里的和
# 如果和等于预期，把结果保存下来，最终输出所有结果
# 注意点：list为可变变量，每次保存的时候用切片实现拷贝
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        # write code here
        if not root:
            return []

        path_stack = []
        res = []

        def preOrderTraversal(pRoot):
            path_stack.append(pRoot.val)

            # 如果pRoot是叶子节点
            if not pRoot.left and not pRoot.right:
                sum = 0
                for i in path_stack:
                    sum += i

                if sum == expectNumber:
                    res.append(path_stack[:])

                path_stack.pop()
            else:
                if pRoot.left:
                    preOrderTraversal(pRoot.left)

                if pRoot.right:
                    preOrderTraversal(pRoot.right)

                path_stack.pop()

        preOrderTraversal(root)

        return res

发表于 2020-01-17 16:35:10 回复(0)

Python

海大_Man

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def FindPath(self, root,target_number):
        '''
        result =[]
        if not root:
            return result
        if not root.left and not root.right and root.val == target_number:
            return [[root.val]]
        else:
            left = self.FindPath(root.left,target_number - root.val)
            right = self.FindPath(root.right,target_number - root.val)
            for item in left+right:
                result.append([root.val]+item)
            return result
        '''
        
        #递归解法：输出二叉树的从根结点到每个叶子节点的路径
        result = []
        if root == None:
            return result
        self.sums = target_number
        self.DFS(root,result,[root.val])
        return result
        
    def DFS(self,root,result,path):
        if root.left == None and root.right == None and sum(path) == self.sums:
            result.append(path)
        if root.left != None:
            self.DFS(root.left,result,path +[root.left.val])
        if root.right != None:
             self.DFS(root.right,result,path + [root.right.val])







# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def FindPath(self, root,target_number):
        '''
        result =[]
        if not root:
            return result
        if not root.left and not root.right and root.val == target_number:
            return [[root.val]]
        else:
            left = self.FindPath(root.left,target_number - root.val)
            right = self.FindPath(root.right,target_number - root.val)
            for item in left+right:
                result.append([root.val]+item)
            return result
        '''
        
        #递归解法：输出二叉树的从根结点到每个叶子节点的路径
        '''
        result = []
        if root == None:
            return result
        self.sums = target_number
        self.DFS(root,result,[root.val])
        return result
        
    def DFS(self,root,result,path):
        if root.left == None and root.right == None and sum(path) == self.sums:
            result.append(path)
        if root.left != None:
            self.DFS(root.left,result,path +[root.left.val])
        if root.right != None:
            self.DFS(root.right,result,path + [root.right.val])
    '''
        #非递归解法
        result = []
        if root == None:
            return result
        stack = []
        stack.append((root,[root.val]))
        while stack:
            node,path = stack.pop(0)
            if node.left == None and node.right == None and sum(path) == target_number:
                result.insert(0,path)
            if node.left != None:
                stack.append((node.left,path + [node.left.val]))
            if node.right != None:
                stack.append((node.right,path + [node.right.val]))
        return result

编辑于 2019-12-28 09:34:21 回复(0)

Python

黄沙遮天

class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def dnspath(self,result,root,path):
        if root.left==None and root.right==None and sum(path)==self.sums:
            result.append(path)
        if root.left!=None:
            self.dnspath(result,root.left,path+[root.left.val])
        if root.right!=None:
            self.dnspath(result,root.right,path+[root.right.val])
    def FindPath(self, root, expectNumber):
        # write code here
        result=[]
        #此处用的self属性，则代表在该对象中sums属性对所有函数都是可见的
        self.sums=expectNumber
        if root==None:
            return result
        else:
            self.dnspath(result,root,[root.val])
            if len(result)!=0:
              #result.sort方法无返回，但是result已经被改变了
              result.sort(key = lambda i:len(i),reverse=True)
              return result
            else:
              return result

本题采用的方法就是先列出其所有根到叶子节点的路径，然后再加上一个对其叶子节点的判断，即此时的列表元素的和是否等于我们最先开始给定的值。需要注意的一点是以后本身对象中的属性尽量用self.xx来表示，不要用全局变量。

发表于 2019-12-16 15:54:25 回复(0)

Python

泼墨20183081312

## 回溯思想：先序遍历二叉树，遇到满足条件的（路径和为零且是叶子节点）记录该路径，记录方法选择插入排序。需要注意的是向res(二维数组)中插入时，path要用path[:]代替，否则结果错误，此处存在疑问，还望大神指点！另外由于python 中的可变对象和不可变对象概念，元组list会随着函数调用发生改变，这种改变会影响全局，因此需要pop()的帮助来“回溯”，而currentsum则不同，与递归一致。

class Solution:

# 返回二维列表，内部每个列表表示找到的路径
def FindPath(self, root, expectNumber):
# write code here
res = []
def Find(node, path, currentsum):
if not node: return
path.append(node.val)
currentsum += node.val
Isleaf = (node.left==None and node.right==None)
if Isleaf and currentsum==expectNumber:
j = 0
for i in range(len(res)):
if len(res[i]) < len(path):
res.insert(i, path[:])
j = 1
break
if j==0: res.append(path[:])
if currentsum < expectNumber:
Find(node.left, path, currentsum)
Find(node.right, path, currentsum)
path.pop()

Find(root, [], 0)

return res

发表于 2019-12-10 10:23:34 回复(0)

Python

但行好事-莫问前程

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def __init__(self):
        self.list_=[]
        self.list_All=[]
    def FindPath(self, root, expectNumber):
        # write code here
        if root==None:
            return self.list_All
        self.list_.append(root.val)
        expectNumber-=root.val
        if expectNumber==0 and root.left==None and root.right==None:
            temp=[i for i in self.list_]
            self.list_All.append(temp)
        self.FindPath(root.left,expectNumber)
        self.FindPath(root.right,expectNumber)
        self.list_.pop()
        return self.list_All

发表于 2019-11-21 11:24:48 回复(0)

提交观点

问题信息

树

难度：

78条回答 4437收藏 179877浏览

通过挑战的用户

Elastic...

2023-02-03 18:01:25
帮内推快手

2022-12-09 17:02:09
牛客85152...

2022-09-19 13:04:27
想成为大佬的小菜鸡

2022-09-16 15:53:26
GzmhaNZ

2022-09-16 12:51:57

二叉树中和为某一值的路径(二)

输入

输出

说明

输入

输出

输入

输出

输入

输出

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题