http://www.vkadoo.cn/B03735571DC135B35FE7C2ED39549238.AHtml
https://discuss.leetcode.com/topic/101111/java-solution-represent-tree-using-hashmap
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.
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.
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.
https://discuss.leetcode.com/topic/101111/java-solution-represent-tree-using-hashmap
How do we solve problem like this if we were given a normal tree? Yes, traverse it, keep a root to leaf running sum. If we see a leaf node (node.left == null && node.right == null), we add the running sum to the final result.
Now each tree node is represented by a number. 1st digits is the
level
, 2nd is the position
in that level
(note that it starts from 1
instead of 0
). 3rd digit is the value. We need to find a way to traverse this tree
and get the sum.
The idea is, we can form a
Formula: For node
tree
using a HashMap. The key
is first two digits which marks the position of a node in the tree. The value
is value of that node. Thus, we can easily find a node's left and right children using math.Formula: For node
xy?
its left child is (x+1)(y*2-1)?
and right child is (x+1)(y*2)?
Given above HashMap and formula, we can traverse the
tree
. int sum = 0;
Map<Integer, Integer> tree = new HashMap<>();
public int pathSum(int[] nums) {
if (nums == null || nums.length == 0) return 0;
for (int num : nums) {
int key = num / 10;
int value = num % 10;
tree.put(key, value);
}
traverse(nums[0] / 10, 0);
return sum;
}
private void traverse(int root, int preSum) {
int level = root / 10;
int pos = root % 10;
int left = (level + 1) * 10 + pos * 2 - 1;
int right = (level + 1) * 10 + pos * 2;
int curSum = preSum + tree.get(root);
if (!tree.containsKey(left) && !tree.containsKey(right)) {
sum += curSum;
return;
}
if (tree.containsKey(left)) traverse(left, curSum);
if (tree.containsKey(right)) traverse(right, curSum);
}
https://discuss.leetcode.com/topic/101116/c-java-clean-code 0
0 1
0 1 2 3
0 1 2 3 4 5 6 7
Regardless whether these nodes exist:
the position of left child is always
the position of right child is always
the position of parent is always
parent_pos * 2
;the position of right child is always
parent_pos * 2 + 1
;the position of parent is always
child_pos / 2
;