[Java solution]Deserialization way


  • 0
    Y

    step 1: deserialization of the tree according to level order traversal representation.
    iterate over the nums
    step 1.1 get the parent node by using the first two digits information of the current element
    step 1.1.1 we can use a map to record the 1:1 relationship between the first two digits and a node.
    step 1.2 build up the parent - child relationship between the parent found and the current element.
    step 2: use top-down recursive way to get the path sum

    class Solution {
        public int pathSum(int[] nums) {
            if (nums == null || nums.length == 0)   return 0;
            Map<Integer, Node> map = new HashMap<>();
            Node head = new Node(nums[0] % 10);
            map.put(nums[0] / 10, head);
            for (int i = 1; i < nums.length; i++) {
                int idx = nums[i] / 10 - (nums[i] / 100) * 10;
                int parentIdx = (nums[i] / 100 - 1) * 10 + (idx % 2 == 0 ? idx / 2: (idx + 1) / 2);
                Node parent = map.get(parentIdx);
                Node newNode = new Node(nums[i] % 10);
                if (idx % 2 != 0)   parent.left = newNode;
                else                parent.right = newNode;
                map.put(nums[i] / 10, newNode);
            }
            int[] sum = new int[1];
            getSum(head, 0, sum);
            return sum[0];
        }
        public void getSum(Node node, int prev, int[] sum) {
            if (node.left == null && node.right == null) {
                sum[0] += prev + node.val;
                return;
            }
            if (node.left != null)      getSum(node.left, prev + node.val, sum);
            if (node.right != null)     getSum(node.right, prev + node.val, sum);
        }
    }
    class Node{
        int val;    Node left;  Node right;
        public Node(int val) {
            this.val = val;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.