學習路線/樹 — 深度優先搜尋 (DFS)

404. 左葉之和

Easy

Sum of Left Leaves

TreeDepth-First SearchBinary TreeRecursion

題目描述

給定一棵二元樹的根節點 root，回傳所有左葉節點的值之和。左葉節點定義為：是父節點的左子節點，且本身沒有任何子節點。

LeetCode 404原題連結 →

解法思路

  1. 使用 DFS 遞迴，透過 is_left 參數標記當前節點是否為左子節點呼叫
  2. 基礎情況：節點為 None 時回傳 0
  3. 到達葉節點時，若 is_left=True 則回傳節點值，否則回傳 0
  4. 非葉節點：回傳 dfs(left, True) + dfs(right, False) 的總和

複雜度分析

  • 時間複雜度：O(n)
  • 空間複雜度：O(h)，h 為樹的高度
3920157
演算法準備開始。目標：找出所有左葉節點（左子節點 + 無子節點）並加總。用 is_left 參數追蹤每次遞迴是否為左側呼叫。
1 / 12