Saturday, November 1, 2014

Facebook: High-Frequency I

1. Calculate the square root of a int
Leetcode: Implement int sqrt(int x).

Idea: Binary search.

public class Solution {
    public int sqrt(int x) {
        if (x == 0) {
            return 0;
        }
        
        if (x < 0) {
            return -1;
        }
        
        long lo = 0;
        long hi = x / 2 + 1;
        
        while (lo <= hi) {
            long mid = lo + (hi - lo) / 2;
            long sq = mid * mid;
            if (sq == x) {
                return (int) mid;
            }
            
            if (sq < x) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        
        return (int) hi;
    }
}

Method2: Newton iterations.

Follow-up: Calculate the sqrt of a double



2. Merge Intervals
 Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
public class Solution {
    public List<Interval>merge(List<Interval> intervals) {
        List<Interval> result = new ArrayList<Interval>();
        
        if (intervals == null || intervals.size() <= 1) {
            return intervals;
        }
        
        // sort the intervals according to the start
        Collections.sort(intervals, new IntervalsComparator());
        
        //result.add(intervals.get(0));
        Interval prev = intervals.get(0);
        for (int i = 1; i < intervals.size(); i++) {
            Interval curr = intervals.get(i);
            if (isOverlapped(prev, curr)) {
                int left = Math.min(prev.start, curr.start);
                int right = Math.max(prev.end, curr.end);
                Interval temp = new Interval(left, right);
                prev = temp;
            } else {
                result.add(prev);
                prev = curr;
            }
        }
        
        result.add(prev);
        
        return result;
    }
    
    private boolean isOverlapped(Interval a, Interval b) {
        return b.start <= a.end;
    }
    
    private class IntervalsComparator implements Comparator<Interval> {
        public int compare(Interval a, Interval b) {
            return a.start - b.start;
        }
    }
}

Follow-up:
Given n intervals [si, fi], find the maximum number of overlapping intervals
A wrong solution:
public class Solution {
    public int maxIntervals(List<Interval> intervals) {
        if (intervals == null || intervals.size() == 0) {
            return 0;
        }
        
        if (intervals.size() == 1) {
            return 1;
        }
        
        int count = 1;
        int max = 1;
        
        // Sort the intervals based on start
        Collections.sort(intervals, new IntervalComparator());
        
        Interval prev = intervals.get(0);
        
        for (int i = 1; i < intervals.size(); i++) {
            Interval curr = intervals.get(i);
            if (curr.start <= prev.end) {
                int left = Math.min(curr.start, prev.start);
                int right = Math.max(curr.end, prev.end);
                prev = new Interval(left, right);
                
                count++;
                max = Math.max(count, max);
            } else {
                prev = curr;
                count = 1;
            }
        }
        return max;
    }
    
    private class IntervalComparator implements Comparator<Interval> {
        public int compare(Interval a, Interval b) {
            return a.start - b.start;
        }
    }
}

Why it is wrong:

Take an example, e.g. [1, 7], [2, 3] [4, 5]. The solution above will get the result of 3, which actually should be 2 instead. 

The correct solution:
public class Solution {
    public int numOverLaps(List<Integer> start, List<Integer> end) {
        if (start == null || start.size() == 0 || end == null || end.size() == 0) {
            return 0;
        }
        
        if (start.size() != end.size()) {
            return 0;
        }
        
        Collections.sort(start);
        Collections.sort(end);
        
        int startP = 0;
        int endP = 0;
        
        int numActive = 0;
        int numOverlap = 0;
        
        while (startP < start.size() && endP < end.size()) {
            if (start.get(startP) < end.get(endP)) {
                numActive++;
                numOverlap = Math.max(numOverlap, numActive);
                startP++;
            } else {
                numActive--;
                endP++;
            }
        }
        return numOverlap;
    }

  public static void main(String[] args) {
    Solution sol = new Solution();

    List<Integer> start = new ArrayList<Integer>();
    List>Integer> end = new ArrayList<Integer>();

    start.add(1);
    start.add(2);
    start.add(5);
    start.add(4);

    end.add(3);
    end.add(4);
    end.add(6);
    end.add(7);

    int result = sol.numOverLaps(start, end);

    System.out.println("Result is " + result);
  }
}




3. Find all the anagrams in an array of strings
Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.
A wrong answer:
public class Solution {
    public List<String> anagrams(String[] str) {
        List<String> result = new ArrayList<String>();
        
        if (str == null || str.length <= 1) {
            return result;
        }
        
        Map<String, List<String> map = new HashMap<String, List<String>>();
        
        for (int i = 0; i < str.length; i++) {
            char[] temp = str[i].toCharArray();
            Arrays.sort(temp);
            String curr = temp.toString();
            
            if (!map.containsKey(curr)) {
                List<String> list = new ArrayList<String>();
                list.add(str[i]);
                map.put(curr, list);
            } else {
                List<String> tempList = map.get(curr);
                tempList.add(str[i]);
                map.put(curr, tempList);
            }
        }
        
        // Dump the hash map to result lsit
        for (List<String> list : map.values()) {
            if (list.size() > 1) {
                result.addAll(list);
            }
        }
        
        return result;
    }
}


Submission Result: Wrong Answer

Input:
["",""]
Output:
[]
Expected:
["",""]











Why this answer is wrong:? 

That is simply because of using the temp.toString() method, which is wrong.
Usually there are two methods to convert a char array to string:
1. Use string constructor: String newString = new String(charArr);
2. Use String newString = String.valueOf(charArr);

So the correct solution is:

public class Solution {
    public List<String> anagrams(String[] str) {
        List<String> result = new ArrayList<String>();
        
        if (str == null || str.length <= 1) {
            return result;
        }
        
        Map<String, List<String> map = new HashMap<String, List<String>>();
        
        for (int i = 0; i < str.length; i++) {
            char[] temp = str[i].toCharArray();
            Arrays.sort(temp);
            String curr = new String[temp];
            
            if (!map.containsKey(curr)) {
                List<String> list = new ArrayList<String>();
                list.add(str[i]);
                map.put(curr, list);
            } else {
                List<String> tempList = map.get(curr);
                tempList.add(str[i]);
                map.put(curr, tempList);
            }
        }
        
        // Dump the hash map to result lsit
        for (List<String> list : map.values()) {
            if (list.size() > 1) {
                result.addAll(list);
            }
        }
        
        return result;
    }
}

4. Combinations (n, k) -- print all combinations of k out of n items
public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (n <= 0 || k <= 0 || n < k) {
            return result;
        }
        
        int[] num = new int[n];
        for (int i = 0; i < n; i++) {
            num[i] = i + 1;
        }
        
        List<Integer> curr = new ArrayList<Integer>();
        combineHelper(num, k, 0, 0, curr, result);
        
        return result;
    }
    
    private void combineHelper(int[] num, int k, int start, int count, List<Integer> curr, List<List<Integer>> result) {
        if (count == k) {
            result.add(new ArrayList<Integer>(curr));
            return;
        }
        
        for (int i = start; i < num.length; i++) {
            curr.add(num[i]);
            combineHelper(num, k, i + 1, count + 1, curr, result);
            curr.remove(curr.size() - 1);
        }
    }
}

Note that we don't need to check start > num.length here because we have guaranteed that k <= n. That is an error-prone point for combination problem.


5. Print a Binary Tree L-R
Binary Tree Level Order Traversal II

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        
        if (root == null) {
            return result;
        }
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> curList = new ArrayList<Integer>();
            
            for (int i = 0; i < size; i++) {
                TreeNode currNode = queue.poll();
                curList.add(currNode.val);
                
                if (currNode.left != null) {
                    queue.offer(currNode.left);
                }
                
                if (currNode.right != null) {
                    queue.offer(currNode.right);
                }
            }
            
            result.add(0, curList);
        }
        
        return result;       
    }
}

6. Implement a LRU cache


7. Find all 3 items that sum to 0 in an array
Given an array S of n integers, are there elements abc in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
  • Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
  • The solution set must not contain duplicate triplets.
    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

Code (Java):
public class Solution {
    public List<List<Integer>> threeSum(int[] sum) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (sum == null || sum.length < 3) {
            return result;
        }
        
        Arrays.sort(sum);
        
        for (int i = 0; i < sum.length - 2; i++) {
            if (i != 0 && sum[i] == sum[i - 1]) {
                continue;
            }
            
            int lo = i + 1;
            int hi = sum.length - 1;
            
            while (lo < hi) {
                int total = sum[i] + sum[lo] + sum[hi];
                
                if (total == 0) {
                    List<Integer> temp = new ArrayList<Integer>();
                    temp.add(sum[i]);
                    temp.add(sum[lo]);
                    temp.add(sum[hi]);
                    result.add(temp);
                    lo++;
                    hi--;
                
                    while (lo < hi && sum[lo] == sum[lo - 1]) {
                        lo++;
                    }
                
                    while (lo < hi && sum[hi] == sum[hi + 1]) {
                        hi--;
                    }
                } else if (total > 0) {
                    hi--;
                } else {
                    lo++;
                }
            }
        }
        
        return result;
    }
}


8. Find the longest palindrome in a given string
public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }
        int n = s.length();
        boolean palin[][] = new boolean[n][n];
        
        String result = "";
        int maxLen = 1;
        
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if ((s.charAt(i) == s.charAt(j) && (j - i) < 2)||
                    (s.charAt(i) == s.charAt(j) && palin[i + 1][j - 1] == true)) {
                        palin[i][j] = true;
                        if (j - i + 1 > maxLen) {
                            result = s.substring(i, j + 1);
                            maxLen = j - i + 1;
                        }
                }
            }
        }
        
        return result;
    }
}


9. Write a palindrome-checking function
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.
Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.
Code (Java):
public class Solution {
    public boolean isPalindrome(String s) {
        if (s == null || s.length() < 2) {
            return true;
        }
        
        // Use regx to remove non-alpha numeric characters
        String delim = "[^a-zA-Z0-9]";
        s = s.replaceAll(delim, "").toLowerCase();
        
        if (s.length() < 2) {
            return true;
        }
        
        int lo = 0;
        int hi = s.length() - 1;
        
        while (lo < hi) {
            if (s.charAt(lo) == s.charAt(hi)) {
                lo++;
                hi--;
            } else {
                return false;
            }
        }
        
        return true;
    }
}

Take away message: string replaceAll(rgex)


10. Reverse Linked list II
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULLm = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given mn satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.
Code (Java):
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null || head.next == null || m == n) {
            return head;
        }
        
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        
        ListNode p = dummyNode;
        int i = 0;
        while (i < m - 1) {
            p = p.next;
            i++;
        }
        
        p.next = reverseList(p.next, n - m + 1);
        
        return dummyNode.next; 
    }
    
    private ListNode reverseList(ListNode head, int len) {
        ListNode prev = null;
        ListNode curr = head;
        
        for (int i = 0; i < len; i++) {
            ListNode nextNode = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextNode;
        }
        
        // connect to the later nodes
        head.next = curr;
        
        return prev;
    }
}

11. Best time to buy and sell stock
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }
        
        int minBuyPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        
        for (int i = 0; i < prices.length; i++) {
            minBuyPrice = Math.min(minBuyPrice, prices[i]);
            maxProfit = Math.max(maxProfit, prices[i] - minBuyPrice);
        }
        
        return maxProfit;
    }
}

12.  Best time to buy and sell stock II
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }
        
        int start = 0;
        int maxProfit = 0;
        
        for (int i = 0; i < prices.length; i++) {
            if (i != 0 && prices[i] < prices[i - 1]) {
                maxProfit += prices[i - 1] - prices[start];
                start = i;
            }
        }
        
        maxProfit += prices[prices.length - 1] - prices[start];
        
        return maxProfit;
    }
}

13.  Best time to buy and sell stock III
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }
        
        int[] leftMax = new int[prices.length];
        int[] rightMax = new int[prices.length];
        
        int minBuy = Integer.MAX_VALUE;
        int maxProfit = 0;
        for (int i = 0; i < prices.length; i++) {
            minBuy = Math.min(minBuy, prices[i]);
            maxProfit = Math.max(maxProfit, prices[i] - minBuy);
            leftMax[i] = maxProfit;
        }
        
        int maxSell = Integer.MIN_VALUE;
        maxProfit = 0;
        for (int i = prices.length - 1; i >= 0; i--) {
            maxSell = Math.max(maxSell, prices[i]);
            maxProfit = Math.max(maxProfit, maxSell - prices[i]);
            rightMax[i] = maxProfit;
        }
        
        maxProfit = 0;
        for (int i = 0; i < prices.length; i++) {
            maxProfit = Math.max(maxProfit, leftMax[i] + rightMax[i]);
        }
        
        return maxProfit;
    }
}


14. Multiply Strings
Given two numbers represented as strings, return multiplication of the numbers as a string.
Note: The numbers can be arbitrarily large and are non-negative.
15. Roman to Integer
Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
public class Solution {
    public int romanToInt(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        int result = 0;
        int i = 0;
        
        Map<String, Integer> map = constructMap();
        
        while (i < s.length()) {
            String curr = s.substring(i, i + 1);
            if ((curr.equals("C") || curr.equals("X") || curr.equals("I")) && (i < s.length() - 1)) {
                String temp = s.substring(i, i + 2);
                if (map.containsKey(temp)) {
                    result += map.get(temp);
                    i++;
                } else {
                    result += map.get(curr);
                }
            } else {
                result += map.get(curr);
            }
            i++;
        }
        
        return result;
    }
    
    private Map<String, Integer>constructMap() {
        Map<String, Integer> map = new HashMap<String, Integer>();
        
        map.put("M", 1000);
        map.put("CM", 900);
        map.put("D", 500);
        map.put("CD", 400);
        map.put("C", 100);
        map.put("XC", 90);
        map.put("L", 50);
        map.put("XL", 40);
        map.put("X", 10);
        map.put("IX", 9);
        map.put("V", 5);
        map.put("IV", 4);
        map.put("I", 1);
        
        return map;
    }
}

A neat solution:
public class Solution {
    public int romanToInt(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        int result = 0;
        int i = 0;
        
        Map<Character, Integer> map = constructMap();
        
        while (i < s.length()) {
            if (i < s.length() - 1 && map.get(s.charAt(i)) < map.get(s.charAt(i + 1))) {
                result -= map.get(s.charAt(i));
            } else {
                result += map.get(s.charAt(i));
            }
            i++;
        }
        
        return result;
    }
    
    private Map<Character, Integer> constructMap() {
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        
        map.put('M', 1000);
        map.put('D', 500);
        map.put('C', 100);
        map.put('L', 50);
        map.put('X', 10);
        map.put('V', 5);
        map.put('I', 1);
        
        return map;
    }
}


16. Integer to Roman
public class Solution {
    public String intToRoman(int num) {
        if (num < 1 && num > 3999) {
            return "";
        }
        
        String[] roman = new String[]{"I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M"};
        int[]    digit = new int[]{1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000};
        
        StringBuilder sb = new StringBuilder();
        for (int i = digit.length - 1; i >= 0; i--) {
            while (num >= digit[i]) {
                sb.append(roman[i]);
                num -= digit[i];
            }
        }
        
        return sb.toString();
    }
}


17. Merge k-sorted list
Method 1: Divide-and Conquer
public class Solution {
    public ListNode mergeKLists(List<ListNode> lists) {
        if(lists == null || lists.size() == 0) {
            return null;
        }
        
        if (lists.size() == 1) {
            return lists.get(0);
        }
        
        return mergeHelper(0, lists.size() - 1, lists);
    }
    
    private ListNode mergeHelper(int lo, int hi, List<ListNode> lists) {
        if (lo == hi) {
            return lists.get(lo);
        }
        
        int mid = lo + (hi - lo) / 2;
        
        // divide
        ListNode left = mergeHelper(lo, mid, lists);
        ListNode right = mergeHelper(mid + 1, hi, lists);
        
        // Conquer
        return mergeTwoLists(left, right);
    }
    
    private ListNode mergeTwoLists(ListNode left, ListNode right) {
        if (left == null) {
            return right;
        }
        
        if (right == null) {
            return left;
        }
        
        ListNode dummyNode = new ListNode(0);
        ListNode p = left;
        ListNode q = right;
        ListNode curr = dummyNode;
        
        while (p != null && q != null) {
            if (p.val <= q.val) {
                curr.next = p;
                p = p.next;
                curr = curr.next;
            } else {
                curr.next = q;
                q = q.next;
                curr = curr.next;
            }
        }
        
        if (p != null) {
            curr.next = p;
        } else if (q != null) {
            curr.next = q;
        }
        
        return dummyNode.next;
    }
}


Method 2: Use a heap
public class Solution {
    public ListNode mergeKLists(List<ListNode> lists) {
        if (lists == null || lists.size() == 0) {
            return null;
        }
        
        PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(lists.size(), new PriorityQueueComparator());
        
        for (ListNode node : lists) {
            if (node != null) {
                pq.offer(node);
            }
        }
        
        ListNode dummyNode = new ListNode(0);
        ListNode curr = dummyNode;
        
        while (!pq.isEmpty()) {
            ListNode temp = pq.poll();
            curr.next = temp;
            curr = curr.next;
            
            if (temp.next != null) {
                pq.offer(temp.next);
            }
        }
        
        return dummyNode.next;
    }
    
    private class PriorityQueueComparator implements Comparator<ListNode> {
        public int compare(ListNode a, ListNode b) {
            return a.val - b.val;
        }
    }
}

Take-away message:

  1. Before careful the node is null the first time inserting a node into the pq
  2. How to create a pq, and implements the comparator
  3. Compare with Collections.sort(Array, new Comparator());

18. Print all the paths from root to every leaf in a binary tree
public class Solution {
    public List<List<Integer>> printPath(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (root == null) {
            return result;
        }
        
        List<Integer> curr = new ArrayList<Integer>();
        printPathHelper(root, curr, result);
        
        return result;
    }
    
    private void printPathHelper(TreeNode root, List<Integer> curr, List<List<Integer>> result) {
        if (root == null) {
            return;
        }
        
        curr.add(root.val);
        
        if (root.left == null && root.right == null) {
            result.add(new ArrayList<Integer>(curr));
            return;
        }
        
        if (root.left != null) {
          printPathHelper(root.left, curr, result);
          curr.remove(curr.size() - 1);
        }   
        
        if (root.right != null) {
          printPathHelper(root.right, curr, result);
          curr.remove(curr.size() - 1);
        }
    }
 }

Take-away message:
Note that we must check root.left and root.right before we go to the root's children. That is because we need to delete the node after we traverse it. For e.g. 
   1
     \
       3
If we don't check that, the node 1 will be deleted.

Another Solution just print the path:
public void printPaths() { 
  int[] path = new int[1000]; 
  printPaths(root, path, 0); 
}

private void printPaths(Node node, int[] path, int pathLen) { 
  if (node==null) return;

  // append this node to the path array 
  path[pathLen] = node.data; 
  pathLen++;

  // it's a leaf, so print the path that led to here 
  if (node.left==null && node.right==null) { 
    printArray(path, pathLen); 
  } 
  else { 
  // otherwise try both subtrees 
    printPaths(node.left, path, pathLen); 
    printPaths(node.right, path, pathLen); 
  } 
}

Follow-up: How to do it iteratatively?
public class Solution {
    public void printPath(TreeNode root) {
        if (root == null) {
            return;
        }
        
        Stack<TreeNode> nodeStack = new Stack<TreeNode>();
        Stack<Integer> levelStack = new Stack<Integer>();
        
        int[] path = new int[1000];
        
        nodeStack.push(root);
        levelStack.push(0);
        
        while (!nodeStack.isEmpty()) {
            TreeNode curr = nodeStack.pop();
            int level = levelStack.pop();
            
            path[level] = curr.val;
            
            if (curr.left == null && curr.right == null) {
                printCurrPath(path, level + 1);
                continue;
            }
            
            if (curr.right != null) {
                nodeStack.push(curr.right);
                levelStack.push(level + 1);
            }
            if (curr.left != null) {
                nodeStack.push(curr.left);
                levelStack.push(level + 1);
            }
        }
    }
}

19. Print the sum of all the numbers at every vertical level in a binary tree
Idea is similar to the question above.
Recursive solution:
public class Solution {
    public void pathSum(TreeNode root) {
        if (root == null) {
            return;
        }
        
        pathSumHelper(root, 0);
    }
    
    private void pathSumHelper(TreeNode root, int curSum) {
        if (root == null) {
            return;
        }
        
        curSum += root.val;
        
        if (root.left == null && root.right == null) {
            System.out.println(curSum);
            return;
        }
        
        pathSumHelper(root.left, curSum);
        pathSumHelper(root.right, curSum);
    }
}

Iterative Solution:
public class Solution {
    public void pathSum(TreeNode root) {
        if (root == null) {
            return;
        }
        
        Stack<TreeNode> nodeStack = new Stack<TreeNode>();
        Stack<Integer> sumStack = new Stack<Integer>();
        
        nodeStack.push(root);
        sumStack.push(root.val);
        
        while (!nodeStack.isEmpty()) {
            TreeNode curr = nodeStack.pop();
            int curSum = sumStack.pop();
            
            if (curr.left == null && curr.right == null) {
                System.out.println(curSum);
                continue;
            }
            
            if (curr.right != null) {
                nodeStack.push(curr.right);
                sumStack.push(curSum + curr.right.val);
            }
            
            if (curr.left != null) {
                nodeStack.push(curr.left);
                sumStack.push(curSum + curr.left.val);
            }
        }
    }
}

No comments:

Post a Comment