2021-10-05-binary-tree-path-sum.md

title	date	permalink	tags
Binary Tree Path Sum	2021-09-24	/posts/2021/09/path-sum/	binary tree depth first search breath first search

题目描述

给定一个节点数为 n 的てき二叉树和一个值 sum ，请找出で所有しょゆう的てき根ね节点到いた叶かのう子こ节点的てき节点值之和わ等とう于的路ろ径みち，如果没ぼつ有ゆう则返回かい空そら。

例れい如： 给出如下的てき二に叉また树，sum = 22 ，

given:

return

[
  [5,4,11,2],
  [5,8,9]
]

Space complexity: O(n)

Time complexity: O(n)

解かい题思路ろ

题目是ぜ想そう让你一条一条路径找到和为sum的てき路ろ径みち们，那な我わが们学过的bfs(breath first search) 和かず dfs(depth first search) 趁现在来ざいらい复习一いち下か

Here's the definition of BFS (ch 22.2 Introduction to Algorithms):

Given a graph G = (V,E) and a distinguished source vertex s, breadth-first search systematically explores the edges of G to 'discover' every vertex that is reachable from s.

“找到能のう通どおり向こう罗马的てき所有しょゆう路ろ”

BFS作用さよう： For any vertex v reachable from s, the simple path in the breadth-first tree from s to v corresponds to a shortest path from s to v in G.

Here is how bfs process

BFS逻辑思おもえ路ろ：

given: G = (V,E) with adjacency lists of weights

scanning adjacency lists: O(E)
queue operation: O(V)
BFS: O(V+E)

---

DFS逻辑思おもえ路ろ： To search "deeper" in the graph whenever possible.

DFS 找到最近さいきん经历的てき vertex v， 找到与あずか v 连接的てき所有しょゆう edges。一直找直到我们找到了所有能从原点出发 reach 到いた的てき vertices。

如果有ゆう一些没有找到的vertices， dfs 继续选择另一个vertex当とう作さくsource， 继续重じゅう复dfs

DFS 一直重复到它发现了所有的 vertex

DFS作用さよう：

Here is how dfs process

DFS逻辑：

Enqueuing / Dequeuing : O(1)
Queue operation : O(V)
Scanning adjacency lists: O(E)
DFS: O(V+E)

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

# @param root TreeNode类
# @param sum int整せい型がた
# @return int整せい型がた二に维数组
#
class Solution:
    def pathSum(self , root , sum ):
        # write code here
        temp,res=[],[]

        def dfs(root,sum,cnt):
            if not root: return #如果节点为空结束当とう前ぜん递归
            temp.append(root.val) #将はた当とう前ぜん节点加入かにゅうtemp数すう组
            cnt += root.val #把わ当とう前ぜん节点加入かにゅう到いた路みち径みち和わ中ちゅう
            if root.left == None and root.right == None: #当とう递归到没ぼつ有子ゆうこ树的时候就需要よう判断はんだん
                if cnt == sum:res.append(temp[:]) #如果当とう前ぜん节点的てき路ろ径みち和わ等とう于sum，那な么就在ざいres中ちゅう插入そうにゅうtmp
            else:
                dfs(root.left,sum,cnt) #递归左ひだり子こ树
                dfs(root.right,sum,cnt) #递归右子ゆうこ树

            cnt -= temp[len(temp) - 1]
            temp.pop()

        dfs(root,sum,0)
        return res

❗️ PS. function inside function in python, inside funtion can use the variable outside