leetcode

LeetCode 666. Path Sum IV

Problem

LeetCode 666. Path Sum IV

1. 题目简述

如果一棵树的高度不超过5，则这棵树可以被表示为一列三位数字的数组(数组从小到大排列)，对于每位数字都有其表示的含义：

  1. 百位D表示该节点的深， 1 <= D <= 4
  2. 十位P表示这个数字在该层的位置，1 <= P <= 8
  3. 个位V表示该节点的值，0 <= V <= 9

求所有的从root到leaf的路径和。例如：

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.

2. 算法思路

DFS

此题的算法并不难，之前也有算过类似的题目，难点在于如何将一棵树完整地复原。一种做法是自己定义TreeNode，然后完整复原整棵树；另一种是使用HashMap来巧妙存储树，用HashMap的时候，前两位为key，个位为value，D和P加在一起能够唯一确定一个节点，且其子节点和右节点的key也能过通过数学公式算出来；第三种就是使用数组来储存，因为高度最高也就是4，建立一个二维数组来存储。

3. 解法

  1. 自己定义TreeNode来存储，然后遍历

class Solution {

    class Node {
        Node left, right;
        int val;
        Node(int v) {val = v;
    }

    int res = 0;
    public int pathSum(int[] nums) {
        Node root = new Node(nums[0] % 10);

        // 这个构建方法中，判断左右子树那块没太搞懂，直接抄了
        for (int num: nums) {
            if (num == nums[0]) continue;
            int depth = num / 100, pos = num / 10 % 10, val = num % 10;
            pos--;
            Node cur = root;
            for (int d = depth - 2; d >= 0; --d) {
                if (pos < 1<<d) {
                    if (cur.left == null) cur.left = new Node(val);
                    cur = cur.left;
                } else {
                    if (cur.right == null) cur.right = new Node(val);
                    cur = cur.right;
                }
                pos %= 1<<d;
            }
        }

        dfs(root, 0);
        return res;
    }

    private void dfs(TreeNode root, int currSum) {
        if (root == null) {
            return;
        }

        currSum += root.val;
        if (root.left == null && root.right == null) {
            res += currSum;
            return;
        }

        dfs(root.left, currSum);
        dfs(root.right, currSum);
    }
}
  1. 使用HashMap来遍历整棵树（直接抄了solution）

class Solution {
    int ans = 0;
    Map<Integer, Integer> values;
    public int pathSum(int[] nums) {
        values = new HashMap();
        for (int num: nums)
            values.put(num / 10, num % 10);

        dfs(nums[0] / 10, 0);
        return ans;
    }

    public void dfs(int node, int sum) {
        if (!values.containsKey(node)) return;
        sum += values.get(node);

        int depth = node / 10, pos = node % 10;
        int left = (depth + 1) * 10 + 2 * pos - 1;
        int right = left + 1;

        if (!values.containsKey(left) && !values.containsKey(right)) {
            ans += sum;
        } else {
            dfs(left, sum);
            dfs(right, sum);
        }
    }
}
  1. 我的原始做法，使用数组来存储
class Solution {
    int res = 0;
    public int pathSum(int[] nums) {
        int[][] tree = new int[4][];

        for (int i = 0; i < 4; i++) {
            tree[i] = new int[(int)Math.pow(2, i)];
            Arrays.fill(tree[i], -1);
        }

        for (int x : nums) {
            int d = x / 100;
            int p = (x % 100) / 10;
            int v = x % 10;
            tree[d - 1][p - 1] = v;
        }

        dfs(tree, 0, 0, 0);

        return res;
    }

    private void dfs(int[][] tree, int d, int p, int sum) {
        if (d >= 4 || p >= (int)Math.pow(2, d) || tree[d][p] == -1) {
            return;
        }
        sum += tree[d][p];
        if (d == 3 || (tree[d + 1][2 * p] == -1 && tree[d + 1][2 * p + 1] == -1)) {
            res += sum;
            return;
        }
        dfs(tree, d + 1, 2 * p, sum);
        dfs(tree, d + 1, 2 * p + 1, sum);
    }
}