[LeetCode] Surrounded Regions

Problem Statement (link):

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

Analysis:
Rather than recording the 2D positions for any scanned 'O', a trick is to substitute any border 'O's with another character - here in the Code I use 'Y'. And scan the board again to change any rest 'O's to 'X's, and change 'Y's back to 'O's.

We start searching 'O' from the four borders. I tried DFS first, the OJ gives Runtime error on the 250x250 large board; In the Sol 2 below, I implement BFS instead, and passed all tests.

The time complexity is O(n^2), as in the worst case, we may need to scan the entire board.

Code:
1, DFS

class Solution {
public:
    // dfs - Runtime error on large board 250x250
    void dfs(vector<vector<char>> &board, int r, int c) {
        if (r<0||r>board.size()-1||c<0||c>board[0].size()-1||board[r][c]!='O')
            return;
        board[r][c]='Y';
        dfs(board, r-1, c);
        dfs(board, r+1, c);
        dfs(board, r, c-1);
        dfs(board, r, c+1);
    }
    void solve(vector<vector<char>> &board) {
        if (board.empty() || board.size()<3 || board[0].size()<3)
            return;
        int r=board.size();
        int c=board[0].size();
        // dfs from boundary to inside
        for (int i=0; i<c; i++) {
            if (board[0][i]=='O')
                dfs(board, 0, i);   // first row
            if (board[c-1][i]=='O')
                dfs(board, c-1, i); // last row
        }
        for (int i=0; i<board.size(); i++) {
            if (board[i][0]=='O')
                dfs(board, i, 0);   // first col
            if (board[i][c-1])
                dfs(board, i, c-1); // last col
        }
        // scan entire matrix and set values
        for (int i=0; i<board.size(); i++) {
            for (int j=0; j<board[0].size(); j++) {
                if (board[i][j]=='O')
                    board[i][j]='X';
                else if (board[i][j]=='Y')
                    board[i][j]='O';
            }
        }
    }
};

2, BFS

class Solution {
public:
    void solve(vector<vector<char>> &board) {
        if (board.empty() || board.size()<3 || board[0].size()<3)
            return;
        int r=board.size();
        int c=board[0].size();
        // queues to store row and col indices
        queue<int> qr;
        queue<int> qc;
        // start from boundary
        for (int i=0; i<c; i++) {
            if (board[0][i]=='O') { qr.push(0); qc.push(i); }
            if (board[r-1][i]=='O') { qr.push(r-1); qc.push(i); }
        }
        for (int i=0; i<r; i++) {
            if (board[i][0]=='O') { qr.push(i); qc.push(0); }
            if (board[i][c-1]=='O') { qr.push(i); qc.push(c-1); }
        }
        // BFS
        while (!qr.empty()) {
            int rt=qr.front(); qr.pop();
            int ct=qc.front(); qc.pop();
            board[rt][ct]='Y';
            if (rt-1>=0 && board[rt-1][ct]=='O') { qr.push(rt-1); qc.push(ct); } // go left
            if (rt+1<r && board[rt+1][ct]=='O') { qr.push(rt+1); qc.push(ct); } // go right
            if (ct-1>=0 && board[rt][ct-1]=='O') { qr.push(rt); qc.push(ct-1); } // go up
            if (ct+1<c && board[rt][ct+1]=='O') { qr.push(rt); qc.push(ct+1); } // go down
        }

        // scan entire matrix and set values
        for (int i=0; i<board.size(); i++) {
            for (int j=0; j<board[0].size(); j++) {
                if (board[i][j]=='O') board[i][j]='X';
                else if (board[i][j]=='Y') board[i][j]='O';
            }
        }
    }
};

[LeetCode] Populating Next Right Pointers in Each Node I

Populating Next Right Pointers in Each Node I

Problem Statement (link):

Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Note:

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

Analysis:
BFS using queue is an obvious solution to this problem. However, as we are asked to solve it without using extra space, we gotta find another way.

There are two types of connections:
1) Connect a node's left child to its right child;
2) Connect a node's right child to the node's sibling's left child, when the node doesn't have a sibling, we set its right child's next pointer to NULL;

A key is to the solution is that we need to connect the nodes while we are at their parent level, since we couldn't go back to the parent's sibling for type 2) connection.

The following code shows both recursive and iterative approaches.

Code:
Sol 1 - Recursive

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (!root) return;
        if (root->left)
            root->left->next=root->right;
        if (root->right)
            root->right->next= root->next ? root->next->left:NULL;

        connect(root->left);
        connect(root->right);
    }
};

Sol 2 - Iterative

class Solution {
public:
    void connect(TreeLinkNode *root) {
        while(root!=NULL) {
            TreeLinkNode* firstNode=root;
            while(firstNode!=NULL) {
                if (firstNode->left)
                    firstNode->left->next=firstNode->right;
                if (firstNode->right)
                    firstNode->right->next= firstNode->next ? firstNode->next->left:NULL;

                firstNode=firstNode->next;
            }
            root=root->left;
        }
    }
};

Binary Tree Level-order traversal

Problem Statement:
Implement binary tree level-order traversal.

Analysis:
We usually use queue to realize BFS, the implementation is done in Sol 1. This is a standard BFS algorithm. It requires O(n) space and O(n) time, where n is the number of nodes in the tree.

However, recursion can be used to solve this problem as well, this algorithm is implemented in Sol 2. As we could see, we traverse the tree h time in order to print nodes in each level, where h is the tree height. This leads to the in-efficiency of this algorithm. However, it's good to know that recursion could be used in BFS problems. The overall time complexity is O(n^2), where n is the number of nodes in the tree.

Code:
Sol 1:

void levelOrderIter(TreeNode* root) {
    queue<TreeNode*> q;

    q.push(root);
    while (!q.empty()) {
        TreeNode* tmp=q.front();
        q.pop();
        cout<<tmp->val<<endl;

        if (tmp->left!=NULL) q.push(tmp->left);
        if (tmp->right!=NULL) q.push(tmp->right);
    }
    return;
}

Sol 2:

void levelOrder(TreeNode* root) {
    // height of tree
    int height=getHeight(root);
    // traverse each level
    for (int i=0; i<height; i++)
        printLevel(root, i);
    return;
}

void printLevel(TreeNode* node, int level) {
    if (node==NULL) return;

    if (level==0) {
        cout<<node->val<<endl;
        return;
    }

    printLevel(node->left, level-1);
    printLevel(node->right, level-1);
}

int getHeight(TreeNode* node) {
    if (node==NULL) return 0;
    int lHeight=getHeight(node->left);
    int rHeight=getHeight(node->right);
    return (lHeight>rHeight ? lHeight:rHeight)+1;
}