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;
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 往上傳資訊+左右結果合併