[leetcode-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:

The hundreds digit represents the depth D of this node, 1 <= D <= 4.
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.
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.

思路：

用一个map -- flag记录二叉树是否到了叶节点。用另一个map记录树节点所在位置和对应的值。

先序遍历二叉树，如果到了根节点，将当前路径和pathsum加到返回值总的和ret中。

遍历左子树。

遍历右子树。

void getsum(int level, int pos, map<int, int>& mp, map<int, bool>& flag, int pathsum, int& ret)

{

    if (level >=  || !flag[level *  + pos])return ;//结点不存在

    pathsum += mp[level *  + pos];//当前路径和

    if (!flag[(level + ) *  + pos * ] && !flag[(level + ) *  + pos *  - ])ret += pathsum ;//到了叶节点

    getsum(level+,pos*-,mp,flag,pathsum,ret);

    getsum(level+,pos*,mp,flag,pathsum,ret);

}

int pathSum(vector<int>& nums)

{

    map<int, int>mp;

    map<int, bool>flag;

    int ret=;

    if (nums.size() == ) return ;

    if (nums.size() == )return nums[] % ;

    for (auto n : nums){ mp[n / ] = n % ; flag[n / ] = true; }

    getsum(, , mp, flag, , ret);

    return ret;

}

巴特西

[leetcode-666-Path Sum IV]

最新文章

热门文章