文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

對于一棵深度小于 5 的樹，可以用一組三位十進制整數來表示。

對于每個整數：

• 百位上的數字表示這個節點的深度 D，1 <= D <= 4。
• 十位上的數字表示這個節點在當前層所在的位置 P， 1 <= P <= 8。位置編號與一棵滿二叉樹的位置編號相同。
• 個位上的數字表示這個節點的權值 V，0 <= V <= 9。

給定一個包含三位整數的升序數組，表示一棵深度小于 5 的二叉樹，
請你返回從根到所有葉子結點的路徑之和。

樣例 1: 輸入: [113, 215, 221] 輸出: 12 解釋: 這棵樹形狀如下:3/ \5 1 路徑和 = (3 + 5) + (3 + 1) = 12.樣例 2: 輸入: [113, 221] 輸出: 4 解釋: 這棵樹形狀如下: 3\1 路徑和 = (3 + 1) = 4.

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/path-sum-iv
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• $id=2^{d?1}+p?1$，將 id 和 val 存入哈希 map
• dfs 遍歷

class Solution {unordered_map<int,int> m;//id,valint sum = 0; public:int pathSum(vector<int>& nums) {if(nums.empty()) return 0;for(int i = 0; i < nums.size(); ++i){int pos = (1<<(nums[i]/100 -1)) + nums[i]/10%10 -1;m[pos] = nums[i]%10;}dfs(1, 0);//從root編號1，s 為和0開始dfsreturn sum;}void dfs(int p, int s){if(!m.count(p))return;s += m[p];bool l = m.count(2*p), r = m.count(2*p+1);if(!l && !r){sum += s;return;}dfs(2*p, s);dfs(2*p+1, s);} };

4 ms 10.2 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 666. 路径和 IV（树的遍历）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。