Java solution using iterative traversal


  • 0
    L

    The given array "nums" stores the tree nodes in an order of the breadth first search. We may traverse all the tree nodes iteratively using a queue. When the depth of the head of the queue is two levels smaller than current node (parent-child relation requires one level difference), or the positions of the head of the queue and current node do not match the parent-child relation (left_child.pos = 2 * parent.pos, right_child.pos = 2 * parent.pos + 1, if we define the position in the range of [0, 7]), we just remove the head of the queue until the parent of current node is found. The path sum is added level by level down to the leaves. We add up all leaf nodes visited to get the final answer.

    class Solution {
        class TreeNode {
            int depth, pos, val;
            TreeNode left, right;
            public TreeNode(int depth, int pos, int val) {
                this.depth = depth;
                this.pos = pos;
                this.val = val;
            }
        }
        public int pathSum(int[] nums) {
            int sum = 0;
            Queue<TreeNode> queue = new LinkedList<>();
            for (int num : nums) {
                int d = num / 100; // depth
                int p = (num - 100 * d) / 10; // position
                int v = num - 100 * d - 10 * p; // value
                TreeNode node = new TreeNode(d, p - 1, v);
                if (!queue.isEmpty()) {
                    while (!queue.isEmpty() && (queue.peek().depth < d - 1 || queue.peek().pos != (p - 1) / 2)) { // looking for the parent of current TreeNode
                        TreeNode temp = queue.poll();
                        if (temp.left == null && temp.right == null) // adding up leaves
                            sum += temp.val;
                    }
                    if (queue.peek().pos * 2 == p - 1)
                        queue.peek().left = node;
                    else
                        queue.peek().right = node;
                    node.val += queue.peek().val;
                }
                queue.offer(node);
            }
            while (!queue.isEmpty()) { 
                TreeNode node = queue.poll();
                if (node.left == null && node.right == null) // adding up leaves
                    sum += node.val;
            }
            return sum;
        }
    }
    

Log in to reply
 

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