面试题34：二叉树中和为某一值的路径

题目描述

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

知识点

二叉树，深度遍历

Qiang的思路

这道题是寻找树的路径的问题，显然是一道考察树的深度遍历的问题，当深度遍历到树的叶子节点，同时这条路径上所有节点的总和为题目给定的值的时候就找到了一条路径。

但是题目要求返回的list中，数组长度大的数组靠前，这就要求对遍历的结果进行排序，在做题时，我没有采用最后将结果排序的方法，而是在遍历过程中就完成了排序工作。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import copy
class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def getResult(self, root, expectNumber, deep, path, result, deeps):
        _path=copy.deepcopy(path)
        _path.append(root.val)
        deep+=1
        expectNumber-=root.val
        if root.left==None and root.right==None and expectNumber==0:
            for i in range(len(deeps)):
                if deeps[i]<deep:
                    result.insert(i, _path)
                    deeps.insert(i, deep)
                    return
            result.append(_path)
            deeps.append(deep)
        if root.left!=None:
            self.getResult(root.left, expectNumber, deep, _path, result, deeps)
        if root.right!=None:
            self.getResult(root.right, expectNumber, deep, _path, result, deeps)
            
    def FindPath(self, root, expectNumber):
        # write code here
        if root==None:
            return []
        result = []
        self.getResult(root, expectNumber, 0, [], result, [])
        return result

这道题一个过不了，后来发现后台判断的时候是认为结果数组中的元素是树节点的值，所以在更新path时将节点的值添加到path中，而不是将节点添加进去。

作者原创，如需转载及其他问题请邮箱联系：lwqiang_chn@163.com。
个人网站：https://www.myqiang.top。