Flatten to list, compute "great value", then map back values to the tree


  • 0
    W

    private LinkedList<Integer> flat(TreeNode root)
    {
    LinkedList<Integer> r = new LinkedList<>();
    if (root == null)
    return r;
    List<Integer> lr = flat(root.right);
    r.addAll(lr);
    r.add(root.val);
    List<Integer> ll = flat(root.left);
    r.addAll(ll);
    return r;
    }
    Map<Integer, Integer> m = new HashMap<>();

    private void traverse(TreeNode root)
    {
    if (root == null)
    return;
    root.val = m.get(root.val);
    traverse(root.left);
    traverse(root.right);
    }

     public TreeNode convertBST(TreeNode root) {
        LinkedList<Integer> ll = flat(root);
        
        Iterator<Integer> i = ll.iterator();
        int t = 0; 
        while (i.hasNext())
        {
            int v = i.next();
            t += v;
            m.put(v, t);
        }
        traverse(root);
        
        return root;
     }

  • 0
    W

    Another solution based on recursion and tree structure:

    private int aux(TreeNode root, int parentVal)
    {
    if (root == null)
    return 0;
    int oldVal = root.val;
    root.val += parentVal;
    int rightVal = aux(root.right, parentVal);
    root.val += rightVal;
    int leftVal = aux(root.left, root.val);
    return rightVal+leftVal+oldVal;
    }
    public TreeNode convertBST(TreeNode root) {
    aux(root, 0);
    return root;
    }


Log in to reply
 

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