Java using List to sort values and Map to calculate sum


  • 1

    The idea is simple, traverse the tree once and save all the values into a List, let Collections.sort() do the sorting, then we only need to care about the value that is behind itself in the List - the value is always greater when its index is higher.
    Traverse the list from behind in reverse order and save the value->sum into the map.
    In the last step, assignVal() do the job of assigning new values into the tree.

    public class Solution {
        public TreeNode convertBST(TreeNode root) {
        	if (root == null || (root.left == null && root.right == null)) return root;
            List<Integer> ls = new ArrayList<Integer>();
            traverse(root, ls);
            Collections.sort(ls);
            Map<Integer, Integer> map = new HashMap<Integer, Integer>();
            Iterator<Integer> it = ls.iterator();
            while (it.hasNext()) System.out.println(it.next());
            int size = ls.size();
            for (int i = size - 1; i >= 0; i--) {
            	int val = ls.get(i);
            	if (i == size - 1) map.put(val, val);
            	else {
            		int preVal = ls.get(i + 1), preSum = map.get(preVal);
            		if (val < preVal) map.put(val, preSum + val);
            		else map.put(val, preSum);
            	}
            }
            assignVal(root, map);
            return root;
        }
        
        private void traverse(TreeNode root, List<Integer> ls) {
        	if (root != null) {
        		ls.add(root.val);
        		if (root.left != null) traverse(root.left, ls);
        		if (root.right != null) traverse(root.right, ls);
        	}
        }
        
        private void assignVal(TreeNode root, Map<Integer, Integer> map) {
        	if (root != null) {
        		root.val = map.get(root.val);
        		if (root.left != null) assignVal(root.left, map);
        		if (root.right != null) assignVal(root.right, map);
        	}
        }
    }
    

  • 1
    W

    @BryanBo.Cao said in Java using List to sort values and Map to calculate sum:

    Collections.sort(ls);

    Since this is BSF, the list could be constructed to a sorted one if the right, root, left order is followed in "traverse". This solution is universal for unsorted trees though.


  • 0

    @weirongwang Yes you are right. We could improve this by removing the Collections.sort() and make the best use of the right children of each node.


Log in to reply
 

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