666. Path Sum IV

 

If the depth of a tree is smaller than 5, then this tree can be represented by a list of three-digits integers.

For each integer in this list:

  1. The hundreds digit represents the depth D of this node, 1 <= D <= 4.
  2. The tens digit represents the position P of this node in the level it belongs to, 1 <= P <= 8. The position is the same as that in a full binary tree.
  3. The units digit represents the value V of this node, 0 <= V <= 9.

 

Given a list of ascending three-digits integers representing a binary with the depth smaller than 5. You need to return the sum of all paths from the root towards the leaves.

Example 1:

Input: [113, 215, 221]
Output: 12
Explanation: 
The tree that the list represents is:
    3
   / \
  5   1

The path sum is (3 + 5) + (3 + 1) = 12.

 

Example 2:

Input: [113, 221]
Output: 4
Explanation: 
The tree that the list represents is: 
    3
     \
      1

The path sum is (3 + 1) = 4.

 

这道题还是让我们求二叉树的路径之和,但是跟之前不同的是,树的存储方式比较特别,并没有专门的数结点,而是使用一个三位数字来存的,百位数是该结点的深度,十位上是该结点在某一层中的位置,个位数是该结点的结点值。为了求路径之和,我们肯定还是需要遍历树,但是由于没有树结点,所以我们可以用其他的数据结构代替。比如我们可以将每个结点的位置信息和结点值分离开,然后建立两者之间的映射。比如我们可以将百位数和十位数当作key,将个位数当作value,建立映射。由于题目中说了数组是有序的,所以首元素就是根结点,然后我们进行先序遍历即可。在递归函数中,我们先将深度和位置拆分出来,然后算出左右子结点的深度和位置的两位数,我们还要维护一个变量cur,用来保存当前路径之和。如果当前结点的左右子结点不存在,说明此时cur已经是一条完整的路径之和了,加到结果res中,直接返回。否则就是对存在的左右子结点调用递归函数即可,参见代码如下:

 

解法一:

class Solution {
public:
    int pathSum(vector<int>& nums) {
        if (nums.empty()) return 0;
        int res = 0;
        unordered_map<int, int> m;
        for (int num : nums) {
            m[num / 10] = num % 10;
        }
        helper(nums[0] / 10, m, 0, res);
        return res;
    }
    void helper(int num, unordered_map<int, int>& m, int cur, int& res) {
        int level = num / 10, pos = num % 10;
        int left = (level + 1) * 10 + 2 * pos - 1, right = left + 1;
        cur += m[num];
        if (!m.count(left) && !m.count(right)) {
            res += cur;
            return;
        }
        if (m.count(left)) helper(left, m, cur, res);
        if (m.count(right)) helper(right, m, cur, res);
    }
};

 

下面这种方法是迭代的形式,我们使用的层序遍历,与先序遍历不同的是,我们不能维护一个当前路径之和的变量,这样会重复计算结点值,而是在遍历每一层的结点时,加上其父结点的值,如果某一个结点没有子结点了,才将累加起来的结点值加到结果res中,参见代码如下:

 

解法二:

class Solution {
public:
    int pathSum(vector<int>& nums) {
        if (nums.empty()) return 0;
        int res = 0, cur = 0;
        unordered_map<int, int> m;
        queue<int> q{{nums[0] / 10}};
        for (int num : nums) {
            m[num / 10] = num % 10;
        }
        while (!q.empty()) {
            int t = q.front(); q.pop();
            int level = t / 10, pos = t % 10;
            int left = (level + 1) * 10 + 2 * pos - 1, right = left + 1;
            if (!m.count(left) && !m.count(right)) {
                res += m[t];
            }
            if (m.count(left)) {
                m[left] += m[t];
                q.push(left);
            }
            if (m.count(right)) {
                m[right] += m[t];
                q.push(right);
            }
        }
        return res;
    }
};

 

类似题目:

Path Sum III

Binary Tree Maximum Path Sum

Path Sum II

Path Sum

 

参考资料:

https://discuss.leetcode.com/topic/101111/java-solution-represent-tree-using-hashmap

 

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation