leetcode practice w9

約 2345 字大約 8 分鐘

2025-01-05

前言

本週是 leetcode weekly practice 的第 9 週, 這週一樣繼續來分享 Blind 75 的題目。總共三題, 其中1 題 Easy , 1 題 Medium, 1 題 Hard ,每個都與Binary Tree有關, 那我們一樣直接進入題目環節。

題目要求：定義 node & node 之間的相連為 edge, 彼此相連的 node 叫做 adjacent node, 而數個 adjacent node edges 相連形成 path （其中每一個 node 至多只會相連兩個 edges ）。定義 path sum 為經該 path 中所包含的 node 之 values 總和。 input 一個 binary tree 的 root node, 求其中的 maximum path sum （其中 node value 從 -1000 ~ 1000）

這題真的滿難的, 不愧為 Hard, 想了半天都沒有什麼想法, 於是去翻看 Hint。稀裡糊塗的看到了關鍵想法, 包含 node 的 maximum path 有幾種可能：

同時包含左右子樹與 node
只包含左子樹與 node
只包含右子樹與 node

得到提點的我便在沒有詳細思考下根據上述三種可能實作遞迴程式, 心想難到就這？結果就是大部分 test case 沒有過, max path sum 數字計算對不上。

仔細思考就會發現, 只用上面三個可能去構建 maximum path sum 會有一個盲點, 那就是加總出的 value 有機會不屬於 "合法的 path"。什麼意思？設想一個情境, 遞迴從 Bottom Up 構建 max path sum 時首先出現 1 這個可能, 當該 node 的 parent node 又為 1 這個可能時, 此時計算值會有 node 有三個 edges 相連, 這樣將不是一個合法的 path （參考以下示意圖）。

[leetcode_124_binary_tree_maximum_path_sum_g1.excalidraw]

從上圖中可以看到計算的結果如螢光筆所連接起並不是一個合法的 path （其中 node 20 有三條相鄰的邊）

從以上示意圖中得知, 只考慮原先三種的可能是不足的, 其實還缺少兩種可能, 那就是 Parent-node-left 或 Parent-node-right。當出現 parent 連接 node 時, 勢必只能選能左右子樹其中一個結果, 問題在於要如何有效的寫成遞迴的方式呢？

我們可以在遞迴計算的時候分開計算 result 值與要回傳的值, 來看以下參考解：

function maxPathSum(root){
	let result = -10000;
	//find valid max path for current node
	function traverse(node){
		if(!node) return 0;

		const leftMax = traverse(node.left);
		const rightMax = traverse(node.right);
		const currentNodeMaxPath = Math.max(
			node.val + maxLeft,
			node.val + maxRight,
			node.val + maxLeft + maxRight,
			node.val
		);
		//Note: max valid path 可能出現在 tree 的任意位置, 持續更新紀錄最大值
		if(currentNodeMaxPath > result) result = currentNodeMaxPath;
		//Note: 對於此 node 的 parent node 來說, 只有以下三種能與 parent 形成 valid path
		return Math.max(node.val, node.val + maxLeft, node.val + maxRight);
	}
	const temp = traverse(root);
	if(temp > result) result = temp;

	return result;
}

上述參考解中用 traverse( ) 來遞迴求當前 node 的合法 max Path, 在遞迴的過程中會去計算四種可能性的最大值, 並持續更新 result。而這邊的關鍵在於, traverse( )的 return 值需要剔除會使得 parent node 採用時形成的 invalid path 狀況（也就是 left-node-right), 已確保 traverse 計算的值正確無誤。當用 traverse( ) 遍歷完所有的 node 時, 最終便能得到此 tree 的 max path 結果（不一定包含 root）。

以上參考解的 Time Complexity 為 O(n), Space Complexity 則為 O(logN) ~ O(n) （看樹高決定遞迴）

結語

2025 新年的第一篇 leetcode 挑戰文, 也是 2025 blog 的第一篇文章 ! 2024 年末的時候有發生些有趣的事, 是之前沒有的體驗, 等之後時間比較充裕且確定之後再來寫一篇文來分享分享。下週的 leetcode 挑戰看心情, 也許會換成別的類型的題目, 或是繼續分享 tree 相關的題目, 不過一樣都是 Blind 75 中的題目。那本週的 leetcode 挑戰分享就到這邊了, 下週繼續～

leetcode practice w9

前言

題目

1 - Same Tree

2 - Validate Binary Search Tree

3 - Binary Tree Maximum Path Sum

結語