题解 | #二叉树中和为某一值的路径#
二叉树中和为某一值的路径
http://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca
这个方法有点像DFS，因为要找完整路径，所以一定是从根节点开始，因此选择对二叉树进行前序遍历，每次遍历时判断该节点是否为叶子节点&&路径的和是否等于expectedNumber。记录正确路径时，用了一个栈path实时记录，当到达叶子节点且满足和的要求时，把path append入paths。
另外，记得用数组的深度copy!!!
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: paths=[] def search(self,root,expectNum,path,cnt,path_i): path.append(root) path_i.append(root.val) cnt+=root.val isLeaf=(root.left==None) and (root.right==None) if isLeaf and cnt==expectNum: self.paths.append(path_i.copy()) # path.clear() if root.left!=None: self.search(root.left,expectNum,path,cnt,path_i) if root.right!=None: self.search(root.right,expectNum,path,cnt,path_i) cnt-=root.val path.pop(-1) path_i.pop(-1) # 返回二维列表，内部每个列表表示找到的路径 def FindPath(self, root, expectNumber): if root==None: return None path=[] path_i=[] cnt=0 self.search(root,expectNumber,path,cnt,path_i) return self.paths # write code here
投递金山WPS等公司10个岗位 >
