LeetCode: Graph

101.cpp

// Source: https://leetcode.com/problems/symmetric-tree/
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    bool symmetry(TreeNode* l, TreeNode* r) {
        if (l == nullptr && r == nullptr)  // the parent is a leaf.
            return true;
        if (l == nullptr || r == nullptr) // skew
            return false;
        if (l->val != r->val) 
            return false;
        
        return symmetry(l->left, r->right) && symmetry(l->right, r->left);
    }
    
public:
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr)   
            return true;
        
        return symmetry(root->left, root->right);
    }
};

102.cpp

// Source: https://leetcode.com/problems/binary-tree-level-order-traversal/
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// Definition for a binary tree node.
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution
{
public:
    vector<vector<int>> levelOrder(TreeNode *root)
    {
        vector<vector<int>> res;
        if (root == NULL)
            return res;

        queue<TreeNode *> q;
        q.push(root);
        while (!q.empty())
        {
            vector<int> level;
            int n = q.size();
            for (int i = 0; i < n; i++)
            {
                auto u = q.front();
                level.push_back(u->val);
                if (u->left)
                    q.push(u->left);
                if (u->right)
                    q.push(u->right);
                q.pop();
            }
            res.push_back(level);
        }
        return res;
    }
};

107.cpp

// Source: https://leetcode.com/problems/binary-tree-level-order-traversal-ii/
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> sol;
        if (root == nullptr) return sol;
        
        queue<TreeNode *> q;
        q.push(root);
        while (!q.empty()) {
            vector<int> level;
            int n = q.size();
            for (int i = 0; i < n; i++) {
                auto s = q.front();
                level.push_back(s->val);
                if (s->left)
                    q.push(s->left);
                if (s->right)
                    q.push(s->right);
                q.pop();
            }
            sol.push_back(level);
        }
        reverse(sol.begin(), sol.end());
        return sol;
    }
};

199.cpp

// Source: https://leetcode.com/problems/binary-tree-right-side-view/
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        if (!root) return res;
        
        queue<TreeNode *> q;
        q.push(root);
        
        while (!q.empty()) {
            int n = q.size();
            int r = INT_MIN; // sentinel
            
            while (n--) {
                auto u = q.front();
                q.pop();
                r = u->val;
                if (u->left) q.push(u->left);
                if (u->right) q.push(u->right);
            }
            if (r != INT_MIN)
                res.push_back(r);
        }
        
        return res;
    }
};

572.cpp

// Source: https://leetcode.com/problems/subtree-of-another-tree/
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    bool isIdentical(TreeNode* s, TreeNode* t) {
        if (s == nullptr && t == nullptr)
            return true;
        
        if (s == nullptr || t == nullptr)
            return false;
        
        if (s->val == t->val)
               return isIdentical(s->left, t->left) && 
                      isIdentical(s->right, t->right);
        
        return false;
    }
    
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if (s == nullptr || t == nullptr)
            return false;
        
        if (s->val == t->val && 
            isIdentical(s->left, t->left) && 
            isIdentical(s->right, t->right))
                return true;
        
        return isSubtree(s->left, t) || isSubtree(s->right, t);
    }
};

785.cpp

// Source: https://leetcode.com/problems/is-graph-bipartite/
class Solution {
public:
    bool isBipartite(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<bool> visited(n);
        vector<int> color(n);
        fill(color.begin(), color.end(), -1);
        
        queue<int> q;        
        bool isbipartite = true;
        
        auto bfs = [&] (int source) {
            q.push(source);
            visited[source] = true;
            color[source] = 0;
            
            while (!q.empty() && isbipartite) {
                int u = q.front();
                q.pop();
            
                for (int v: graph[u]) {
                    if (visited[v]) {
                        if (color[u] == color[v]) {
                            isbipartite = false;
                            break;
                        }
                        continue;
                    }
                
                    visited[v] = true;
                    color[v] = 1 ^ color[u];
                    q.push(v);
                }
            }
        };        
        
        for (int u = 0; u < n; u++)
            if (color[u] == -1)
                bfs(u);
        
        return isbipartite;
    }
};

872.cpp

// Source: https://leetcode.com/problems/leaf-similar-trees/
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    vector<int> dfs(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> s;
        s.push(root);
        
        while (!s.empty()) {
            auto u = s.top();
            s.pop();
            if (u->left == nullptr && u->right == nullptr)
                res.push_back(u->val);
            else {
                if (u->left) s.push(u->left);
                if (u->right) s.push(u->right);
            }
        }
        
        return res;
    }
    
public:
    bool leafSimilar(TreeNode* root1, TreeNode* root2) {
        auto v = dfs(root1);
        auto w = dfs(root2);
        bool similar = v.size() == w.size();
        
        if (!similar) return similar;
        
        for (int i = 0, n = v.size(); i < n; i++) {
            if (v[i] != w[i]) {
                similar = false;
                break;
            }
        }
        
        return similar;
    }
};

897.cpp

// Source: https://leetcode.com/problems/increasing-order-search-tree/
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution 
{
private:
    TreeNode* last = nullptr; // last node in the tree built so far.

public:
    TreeNode* increasingBST(TreeNode* root) 
    {
        if (root->left == nullptr && root->right == nullptr)  // leaf
        {
            last = root;
            return root;
        }
        
        if (root->left != nullptr) 
        {
            auto u = increasingBST(root->left);
            last->right = root;
            last = root;
            root->left = nullptr;
            root = u;
        }
        
        root->right = increasingBST(root->right);
        return root;
    }
};