[Java][LeetCode][Tree][BFS][DFS]

SP Hou
Apr 19, 2022

--

試著去用DFS跟BFS來做,兩個都是O(N),沒什麼太大的差別。
DFS:
開一個全域的sum好讓之後左右tree都掃完的時候把值回出去。因為每次都要將上層累計完的值*10再加上自己node的值,所以要把上層計算完的值丟給子節點。直到node的左右兩邊都為空的時候,表示已經掃完全部,就可以跳開這個遞迴。
BFS:
開兩個Queue,一個要放node,一個要放上一層計算完的值,因為一樣要把計算完的值丟給下一層計算,當前的這個node的左右都沒有子節點時,視為該邊已經掃完了,將累計的值丟到List記起來,之後要算總和的時候要用到。當左(右)子節點不為空的時候,把該邊的子節點以及計算好的值丟到相對應的Queue,以便進到下一層。

Implement with DFS and BFS, the time complexity both are O(N).
DFS:
Create a global variable to return the sum when the tree is traversal done. The number of each level is the number of the last level multiple 10 and adds the current node value. The number needs to be delivered to the next level. Until, all nodes were traversed, quite the while loop.
BFS:
Create two Queue, one is to keep the node, and one is to keep the number of the last level calculated. While this side of the tree is traversed, put the number into a list, I will calculate the sum when the two sides of the tree are finished.

--

--