iT邦幫忙

2026 iThome 鐵人賽

DAY 15
1
Software Development

快樂演算法系列 第 15

yolo26m 素材太少了啦& 236 v2

  • 分享至 

  • xImage
  •  

1.* 表示它們是 pointer(指標),也就是「指向某個 TreeNode」

2.node->left從 node 這個 pointer 指到的 TreeNode,取它的 left。

3.if (!node || node == p || node == q)
return node;
分成三種:
!node= 這裡沒有節點= 搜到盡頭了= 回傳 nullptr
node == p = 找到 p= 回傳 p
node == q = 找到 q= 回傳 q

4.往下找 p/q,找到後利用 recursion return 一路往上推

5.最小例子:

    5 = p
     \
      4 = q

DFS 到:node = 5因為:node == p直接:return 5;

  1. 不用繼續找 q 因為題目已經保證 p、q 都存在,而且一個 node 可以是自己的 descendant。5 一定已經是 p 和 q 的共同祖先,而且不可能有比 5 更低又同時包含 p 本人的共同祖先。所以直接回 5。

7.最小流程:

        3
       / \
   p=5   q=1

node = 3
├─ 左邊
│ node = 5
│ node == p
│ return 5

└─ 右邊
node = 1
node == q
return 1

然後 recursion 往上回到 3:

        3
       ↑ ↑
      5   1

left = 5 ; right = 1

if (left && right)
return node;

因為左右都有東西:

左找到 p 右找到 q

目前 node = 3

LCA = 3

return left ? left : right;ternary operator只有一邊找到東西,就把那一邊繼續往上傳。

找到 p/q

回上一層

只有左邊有 → 傳左邊;只有右邊有 → 傳右邊;左右都有 → 當下 node 就是 LCA

8.往下搜尋+利用 recursion return 往上傳資訊+左右結果合併

  1. 往下找,往上判斷;左右都有就回自己,只有一邊有就把那一邊往上傳。

上一篇
rollout & 236
系列文
快樂演算法15
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

1 則留言

0
AndyAWD
iT邦新手 1 級 ‧ 2026-09-03 23:48:27

過一半啦!

我要留言

立即登入留言