[剑指Offer]二叉树中和为某一值的路径

题目描述

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

解题思路

递归递归递归。原理很简单,若当前根节点为空或者大于期望值,终止往下;若当前根节点等于期望值,若为叶子结点,则返回只有当前节点的二维列表,若不为叶子结点,终止往下;若当前根节点小于期望值,则递归往下,最终把递归结果合并起来并排序。

代码

Python(2.7.3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# -*- 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
if root is None or root.val > expectNumber:
# 这里递归调用时返回一维列表并不影响,因为对于空列表做列表合并和循环不影响其他的
return []
if root.val == expectNumber:
if root.left is None and root.right is None:
return [[root.val]]
else:
return []
res = []
expectNumber -= root.val
left = self.FindPath(root.left, expectNumber)
right = self.FindPath(root.right, expectNumber)
# 左右子树都返回二维列表(为空或大于除外),循环取出其中的路径然后与根节点合并加入到res中
for path in left + right:
res.append([root.val] + path)
return sorted(res, key=lambda x: len(x), reverse=True)

运行时间:23ms
占用内存:5684k