Day 90, ##, Binary Tree Upside Down, Read N Characters Given Read4, Read N Characters Given Read4 II - Call multiple times

Binary Tree Upside Down

Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.
For example:
Given a binary tree {1,2,3,4,5},

    1
   / \
  2   3
 / \
4   5

return the root of the binary tree [4,5,2,#,#,3,1].

   4
  / \
 5   2
    / \
   3   1  

----------------------------------------------------------------
Solution #1, recursive

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *helper(TreeNode *root, TreeNode *left, TreeNode *right) {
        if (root == NULL) return right;
        TreeNode *tempLeft = root->left;
        TreeNode *tempRight = root->right;
        root->right = right;
        root->left = left;

        return helper(tempLeft,tempRight,root);
    }

    TreeNode *upsideDownBinaryTree(TreeNode *root) {
        return helper(root,NULL,NULL);
    }
};

Solution #2, iterative, with a stack containing all left children

Read N Characters Given Read4

The API: int read4(char *buf) reads 4 characters at a time from a file.
The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.
By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.
Note:
The read function will only be called once for each test case.
------------------------------------------------------------------

// Forward declaration of the read4 API.
int read4(char *buf);

class Solution {
public:
    /**
     * @param buf Destination buffer
     * @param n   Maximum number of characters to read
     * @return    The number of characters read
     */
    int read(char *buf, int n) {
        int count = 0;
        while (count < n) {
            int curRead = read4(buf);
            if (curRead < 4) {
                return min(count + curRead,n);
            }
            count += curRead;
            buf += 4;
        }
        return n;
    }
};

Java

/* The read4 API is defined in the parent class Reader4.
      int read4(char[] buf); */

public class Solution extends Reader4 {
    /**
     * @param buf Destination buffer
     * @param n   Maximum number of characters to read
     * @return    The number of characters read
     */
    public int read(char[] buf, int n) {
        int count = 0; 
        while (count < n) {
            char[] temp = new char[4];
            int curRead = read4(temp);
            for (int i = 0; i < curRead && count < n; i++) {
                buf[count++] = temp[i];
            }
            if (curRead < 4) break;
        }
        
        return count;
    }
}

Read N Characters Given Read4 II - Call multiple times

The API: int read4(char *buf) reads 4 characters at a time from a file.
The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.
By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.
Note:
The read function may be called multiple times.
----------------------------------------------------------------
Note: char *buf is the destination buffer

// Forward declaration of the read4 API.
int read4(char *buf);

class Solution {
public:
    Solution() {
        bufferSize = 0;
        offset = 0;
    }

    /**
     * @param buf Destination buffer
     * @param n   Maximum number of characters to read
     * @return    The number of characters read
     */
    int read(char *buf, int n) {
        int readChar = 0;
        bool eof = false;
        while (!eof && readChar < n) {
            if (bufferSize == 0) {
                bufferSize = read4(buffer);
                if (bufferSize < 4) {
                    eof = true;
                }
            }
            int len = min(n - readChar,bufferSize);
            memcpy(buf,buffer + offset,len);
            bufferSize -= len;
            offset = (offset + len) % 4;
            readChar += len;
            buf += len;
        }
        
        return readChar;
    }
    
private:
    char buffer[4];
    int offset;
    int bufferSize;
};

Java, 有若干种实现方式，关键在于先把本地的缓存读完，再调用read4

/* The read4 API is defined in the parent class Reader4.
      int read4(char[] buf); */

public class Solution extends Reader4 {
    
    private char[] local = new char[4];
    private int index = 0;
    private int size = 0;
    /**
     * @param buf Destination buffer
     * @param n   Maximum number of characters to read
     * @return    The number of characters read
     */
    public int read(char[] buf, int n) {
        int count = 0;
        boolean eof = false;
        while (count < n && !eof) {
            if (size == 0) {
                size = read4(local);
                index = 0;
                if (size < 4) eof = true;
            }

            while (size > 0 && count < n) {
                buf[count] = local[index];
                count++;
                index++;
                size--;
            }            
        }
        
        return count;
    }
}