[LeetCode] 113. Path Sum II

轉自LeetCode

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

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

<Solution>

這題是 Path Sum 衍生題

不同點在於，這次不是找到是否有 path sum 能符合就好

而是如果有，要把所有的 path 都找出來

因為要找到所有 path，代表要回溯，所以先想到的是 recursive 的解法

解題想法和 Path Sum 一樣，只是要把過程中經過的值記錄下來，並且配合 recursive 做回溯

code 如下
c++

kotlint
和 Path Sum 一樣，有 iterative 的解法，思路也一樣，差別只在於 queue 要存的資訊而已

這邊注意一點是，因為是先檢查 left node，再檢查 right node

所以如果有先 push left node 的值的話，記得也要 pop 掉

不然在 right node 的部分，會多包含到 left node 的值

code 如下