剑指24-二叉树中和为某一值的路径

Posted on | In |

题目描述

输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。返回值的形式是路径节点值的列表集，按节点数量从大到小排列。

  • 思路与八皇后问题相似，下面的代码用了循环和递归，可以轻易地修改成尾递归版本和完全循环的版本。
  • 定义递归函数recur(root, number, k, path)，参数里root是要访问的节点, path的前k个是路径的上游节点。如果有满足条件的路径，则返回路径为元素（也是列表）的列表；如果没有，则返回空列表。
    • 参数root是叶节而且路径满足条件时，要避免调用两次recur(None, number, k, path)，不然满足条件的路径会被重复计入。以此语句应对：if not root.left and not root.right: return recur(None, number-root.val, k+1, path)
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
27
28
class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):        
        def recur(root, number, k, path): # 
            # 要访问root, path的前k个是路径的上游节点
            # 如果有满足条件的路径，则返回列表的列表；如果没有，则返回空列表。
            if root is None:
                if number == 0:
                    if k <= 0:
                        return []
                    else:
                        return [path[:k]]
                else:
                    return []
            else:
                if len(path) == k:
                    path.append(root.val)
                else:
                    path[k] = root.val
                if not root.left and not root.right:
                    return recur(None, number-root.val, k+1, path)
                else:
                    res= recur(root.left, number-root.val, k+1, path)
                    res.extend(recur(root.right, number-root.val, k+1, path))
                    return res
        result = recur(root, expectNumber, 0, [])
        result.sort(key=len, reverse=True)
        return result