二叉树中和为某一值的路径.md

题目描述

输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

解题思路

– 注意到路径必须为跟节点 –> 没有左右子树的叶子节点；定义两个数组pathArray、onePath，pathArray用于存储所有符合条件的路径，onePath用于存储当前遍历的路径； – 类似于深度优先搜索，每遍历到一个节点，就将其加入到onePath中，并判定是否符合条件：

1. 为叶节点且和等于要求的整数，则将该数组存储至pathArray中，并换其他路径继续搜寻；
2. 和小于要求的整数，则向当前节点的左右子树依次深度优先搜索；
3. 和大于要求的整数，则直接换路搜索。

代码草稿

import copy
class Solution:
    def FindPath(self, root, expectNumber):
        onePath = []
        pathArray = []
        self.Find(root, expectNumber, onePath, pathArray)
        return pathArray

    def Find(self, root, expectNumber, onePath, pathArray):
        if root == None:
            return pathArray

        onePath.append(root.val)
        if self.getSum(onePath) == expectNumber and not root.left and not root.right:
            pathArray.append(copy.deepcopy(onePath))
        elif self.getSum(onePath) < expectNumber:
            if root.left != None:
                self.Find(root.left, expectNumber, onePath, pathArray)
                onePath.pop(-1)
            if root.right != None:
                self.Find(root.right, expectNumber, onePath, pathArray)
                onePath.pop(-1)
        elif self.getSum(onePath) > expectNumber:
            onePath.pop(-1)

    def getSum(self, array):
        sum = 0
        for i in array:
            sum += i
        return sum

为了不让其他因素干扰到思路，写代码时完全不考虑美观和简洁；Python是优雅的，好的程序一定是赏心悦目的。如果代码逻辑很丑陋，那一定是自己的问题… 所以现在到了改正自己问题的时候了~：

待优化：

1. 写三个函数，只为实现一个功能；第一个函数只是为了声明变量而存在，第二个函数传入的变量则过多，第三个函数则无存在的必要；
2. 代码不够精炼，数组元素弹出操作、判断节点是否为空的操作均出现多次。

优化后的代码

class Solution:
    def __init__(self):
        self.onePath = []
        self.PathArray = []
    def FindPath(self, root, expectNumber):
        if root is None:
            return self.PathArray
        self.onePath.append(root.val)
        expectNumber -= root.val
        if expectNumber==0 and not root.left and not root.right:
            self.PathArray.append(self.onePath[:])
        elif expectNumber>0:
            self.FindPath(root.left,expectNumber)
            self.FindPath(root.right,expectNumber)
        self.onePath.pop()
        return self.PathArray