Recursion 練習題目

100. Same Tree

  • Bottom-up
  • Top-down

700. Search in a Binary Search Tree

從leaf開始遞歸處理每個節點及其子樹的解答,然後根據節點的值與搜尋值的大小關係來遞歸左右子樹,直到找到目標節點或搜尋失敗。

  • Bottom-up
  • Top-down

從root開始遞歸處理每個節點及其子樹,並根據節點的值與搜尋值的大小關係來遞歸左右子樹,直到找到目標節點或搜尋失敗。

37. Sudoku Solver

  • Bottom-up

這題不能用Bottom-up

  • Top-down

112. Path Sum

  • Bottom-up

從leaf開始遞歸處理每個節點及其子樹的解答,然後將子問題的解答不斷回傳並合併成更高層次的解答,直到回傳整體解答。

  • Top-down

從root開始遞歸處理每個節點及其子樹,並在遞歸的過程中不斷更新當前的總和,直到到達最後leaf節點並得到子問題的解答

104. Maximum Depth of Binary Tree

從leaf開始向上回傳深度,直到根節點。在遞歸時,將左子樹和右子樹的深度比較,取最大值加1,返回當前節點的深度。

  • Bottom-up

  • Top-down

從root開始遍歷整棵樹,往下遍歷子樹並更新目前節點所在子樹的最大深度。當遍歷到葉子節點時,比較當前深度與目前最大深度的大小,如果當前深度更大,就更新最大深度的值。

257. Binary Tree Paths

  • Bottom-up (dfs)
  • Top-down