[LeetCode] Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

Analysis: It's the same question as get Binary Tree Paths

/**
 * 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 {
/**
 * 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 {
    vector<string> getAllPaths(TreeNode * node)
    {
        vector<string> res;
        if(!node) return res;
        string cur = to_string(node->val);
        if(!node->left && !node->right) res.push_back(cur);
        
        if(node->left)
        {
            vector<string> left = getAllPaths(node->left);
            for(auto e :left) res.push_back(cur+e);
            
        }
        if(node->right)
        {
            vector<string> right = getAllPaths(node->right);
            for(auto e :right) res.push_back(cur+e);
        }    
        return res;
    }
public:
    int sumNumbers(TreeNode* root) {
        vector<string> paths = getAllPaths(root);
        int res = 0;
        for(auto e:paths) res += stoi(e);
        return res;
    }
};

[LeetCode] Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note: 
You may assume k is always valid, 1 ≤ k ≤ BST's total elements

Analysis: Note, in order traverse a BST will get a sorted array from smallest to biggest.

    int visit(TreeNode* root, int k, int &i){
        if(!root)   return 0;
        int res = visit(root->left,k,i);
        if(i == k)  return res;
        if(++i == k)    return root->val;
        return visit(root->right,k,i);
    }
    
    int kthSmallest(TreeNode* root, int k) {
        int i=0;
        return visit(root,k,i);
    }

[LeetCode] Binary Search Tree Iterator

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

class BSTIterator {
private:
    stack<TreeNode*> st;
public:
    BSTIterator(TreeNode *root) {
        findLeft(root);
    }

    bool hasNext() {
        if (st.empty()) return false;
        return true;
    }

    int next() {
        TreeNode* top = st.top();
        st.pop();
        if (top->right != NULL)
            findLeft(top->right);
        return top->val;
    }

    void findLeft(TreeNode* root)
    {
        TreeNode* p = root;
        while (p != NULL)
        {
            st.push(p);
            p = p->left;
        }
    }
};

Deep iterator, Nested Lists

Print {1, {2,3}, {4,{5,6},7} with the interfaces hasNext and getNext.

Analysis:

             {1, {2,3}, {4,{5,6},7}
                /              |             \
              1            {2,3}     {4,{5,6},
                            /     \           /   \
                          2        3      4    {5,6}
                                                   /    \
                                                  5     6

Note, there are two types of nodes. One is actual number, the other is a list

As shown above, the problem can be solved by pre order traverse the tree. Simply, we can record the current index of a sub list to know which element should be visited.

class ListNode
{
public:
    std::vector<ListNode*> v;
    int val;
    //curIndex points the element to visit in v, if v is not empty
    //else curIndex == 0 means val is not visited yet.
    int curIndex;

    bool hasNext(){
        if(!v.empty())
        {
            if(curIndex >= v.size()) 
                return false;
            if(!v[curIndex]->hasNext() 
                && curIndex+1 >= v.size())
            {
                return false;
            }
            return true;
        }
        //if the element is visited, curIndex is 1.
        return curIndex == 0;
    }
    int getNext(){
        if(!v.empty())
        {
            if(!v[curIndex]->hasNext()) curIndex++;
            return v[curIndex]->getNext();
        }
        curIndex++;
        return val;
    }
    ListNode(int p){
        curIndex = 0;
        val = p;
    }
};

int main()
{
    ListNode l0(-11), l2(-11), l3(-11), l32(-11);
    ListNode n1(1),n2(2), n3(3),n4(4), n5(5),n6(6),n7(7);

    l32.v.push_back(&n5);
    l32.v.push_back(&n6);

    l3.v.push_back(&n4);
    l3.v.push_back(&l32);
    l3.v.push_back(&n7);

    l2.v.push_back(&n2);
    l2.v.push_back(&n3);

    l0.v.push_back(&n1);
    l0.v.push_back(&l2);
    l0.v.push_back(&l3);

    while(l0.hasNext())
    {
        std::cout << l0.getNext() << "\n";
    }
}

[LintCode] Subtree

You have two every large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.

Example

T2 is a subtree of T1 in the following case:

       1                3
      / \              / 
T1 = 2   3      T2 =  4
        /
       4

T2 isn't a subtree of T1 in the following case:

       1               3
      / \               \
T1 = 2   3       T2 =    4
        /
       4

Note

A tree T2 is a subtree of T1 if there exists a node n in T1 such that the subtree of n is identical to T2. That is, if you cut off the tree at node n, the two trees would be identical.

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    bool isSame(TreeNode *T1, TreeNode *T2)
    {
        if(!T1 && !T2) return true;
        if((T1 && !T2) || (T2 && !T1))return false;
        if(T1->val != T2->val) return false;
        return isSame(T1->left, T2->left) && isSame(T1->right, T2->right);
    }
    bool isSubtree(TreeNode *T1, TreeNode *T2) {
        // write your code here
        
        if((T1 && !T2)|| (!T1 && !T2)) return true;
        if(!T1) return false;

        if(T1->val == T2->val
            && isSame(T1,T2)) return true;
        
        if(isSubtree(T1->left, T2)) return true;
        if(isSubtree(T1->right, T2)) return true;
        return false;
    }
};

[LintCode] Remove Node in Binary Search Tree

Given a root of Binary Search Tree with unique value for each node.  Remove the node with given value. If there is no such a node with given value in the binary search tree, do nothing. You should keep the tree still a binary search tree after removal.

Example

Given binary search tree:

          5

       /    \

    3          6

 /    \

2       4

Remove 3, you can either return:

          5

       /    \

    2          6

      \

         4

or :

          5

       /    \

    4          6

 /   

2

Analysis:

The logic is simple:

1) find the node with the given value;

2) if left subtree is NULL, return the right subtree

3) if right subtree is NULL, return the left subtree

4) find and delete the maximum node in the left subtree,  and replace value( If we want to actually delete the node, that will be more complicated.)

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (!root) return nullptr;
        if (root->val == key) {
            if (!root->right) {
                TreeNode* left = root->left;
                delete root;
                return left;
            }
            else {
                TreeNode* right = root->right;
                while (right->left)
                    right = right->left;
                swap(root->val, right->val);    
            }
        }
        root->left = deleteNode(root->left, key);
        root->right = deleteNode(root->right, key);
        return root;
    }
};

[LeetCode] Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.

Note:
You may assume that all inputs are consist of lowercase letters a-z.

Analysis: There is no need to keep an another class called TrieNode in this case.

class Trie {
public:
    // Initialize your data structure here.
    void insert(string s) {
        Trie *cur = this;
        for(int i=0;i<s.length();i++)
        {
            int index = s[i]-'a';
            if(cur->current[index]==NULL){
                cur->current[index] = new Trie();
            }
            cur = cur->current[index];
        }
        cur->endOfWord = true;
    }

    bool startsWith(string prefix) {
        Trie *cur = this;
        for(int i=0;i<prefix.length();i++)
        {
            cur = cur->current[prefix[i]-'a'];
            if(!cur) return false;
        }
        return true;
    }
    
    bool search(string key)
    {
        Trie *cur = this;
        for(int i=0;i<key.length();i++)
        {
            cur = cur->current[key[i] - 'a'];
            if(!cur) return false;
        }
        return cur->endOfWord;
    }
    
    Trie() {
        endOfWord = false;
        for(int i=0;i<26;i++) current[i]=NULL;
    }
    
    ~Trie(){
        for(int i=0;i<26;i++)
        {
            if(current[i]) delete current[i];
        }
    }
private:
    Trie *current[26];
    bool endOfWord;
};

[LintCode] Lowest Common Ancestor

Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the two nodes.

The lowest common ancestor is the node with largest depth which is the ancestor of both nodes.

Example

        4

    /     \

  3         7

          /     \

        5         6

For 3 and 5, the LCA is 4.

For 5 and 6, the LCA is 7.

For 6 and 7, the LCA is 7.

Method 1: Transform it to the problem of finding the first common node of two linked lists.

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    bool hasNode(vector<TreeNode*> &rec,TreeNode *node, TreeNode *target)
    {
        if(!node) return false;

        if(node == target ||
           hasNode(rec, node->left, target) ||
           hasNode(rec, node->right, target)) 
        {
            rec.push_back(node);
            return true;
        }
        return false;
    }
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *A, TreeNode *B) {
        if(!root) return NULL;
        vector<TreeNode*> recA;
        hasNode(recA, root, A);
        vector<TreeNode*> recB;
        hasNode(recB, root, B);
        
        int lenA = recA.size(), lenB = recB.size();
        if(0 == lenA || 0 == lenB) return NULL;
        int i = lenA-1, j = lenB-1;
        while(i>=0 && j>=0 && recA[i] == recB[j])
        {
            i--;
            j--;
        }
        return recA[i+1];
    }
};

Method 2: Very neat

class Solution {
public:
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *A, TreeNode *B) {
        if(!root) return NULL;
        if(root == A || root == B) return root;
        TreeNode *left = lowestCommonAncestor(root->left, A, B);
        TreeNode *right = lowestCommonAncestor(root->right, A, B);
        if(left && right) return root;
        return left?left:right;
    }
};

[LintCode] Interval Sum II

Given an integer array in the construct method, implement two methods query(start, end) and modify(index, value):

• For query(start, end), return the sum from index start to index end in the given array.
• For modify(index, value), modify the number in the given index to value

Example

Given array A = [1,2,7,8,5].

• query(0, 2), return 10.
• modify(0, 4), change A[0] from 1 to 4.
• query(0, 1), return 6.
• modify(2, 1), change A[2] from 7 to 1.
• query(2, 4), return 14.

class Solution 
{
    class SegmentTreeNode 
    {
    public:
        int start, end, sum;
        SegmentTreeNode *left, *right;
        SegmentTreeNode(int start, int end, int sum) {
            this->start = start;
            this->end = end;
            this->sum = sum;
            this->left = this->right = NULL;
        }
    };
    SegmentTreeNode *build(vector<int>&A, int start, int end)
    {
        if(start == end) return new SegmentTreeNode(start, end, A[start]);
        int mid = (start+end)/2;
        SegmentTreeNode *left = build(A, start, mid);
        SegmentTreeNode *right = build(A, mid+1, end);
        SegmentTreeNode *node = new SegmentTreeNode(start, end, left->sum+right->sum);
        node->left = left;
        node->right = right;
        return node;
    }
    SegmentTreeNode *root;
    long long query(SegmentTreeNode* root, int start, int end)
    {
        if(start == root->start && end == root->end) return root->sum;
        int mid = (root->start + root->end)/2;
        if(end <= mid) return query(root->left, start, end);
        if(start > mid) return query(root->right, start, end);
        return query(root->left, start, mid) + query(mid+1, end);
    }
    int modify(SegmentTreeNode *root, int index, int value) {
    
        if(root->start == root->end && index == root->start) 
        {
            int tmp = value - root->sum;
            root->sum = value;
            return tmp;
        }
        
        int mid = (root->start + root->end)/2;
        int diff;
        if(index <= mid) diff = modify(root->left, index, value);
        else diff = modify(root->right, index, value);
        root->sum += diff;
        return diff;
    }
public:
    Solution(vector<int> A) {
        if(A.size() > 0) root = build(A, 0, A.size()-1);
        else root = NULL;
    }
    long long query(int start, int end) {
        if(!root) return -1;
        return query(root, start, end);
    }
    void modify(int index, int value) {
        if(!root) return;
        modify(root, index, value);
    }
};

[LintCode] Interval Minimum Number

Given an integer array (index from 0 to n-1, where n is the size of this array), and an query list. Each query has two integers[start, end]. For each query, calculate the minimum number between index start and end in the given array, return the result list.

Example

For array [1,2,7,8,5], and queries [(1,2),(0,4),(2,4)], return [2,1,5]

Segment Tree:

/**
 * Definition of Interval:
 * classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 */
class Solution { 
public:
    /**
     *@param A, queries: Given an integer array and an query list
     *@return: The result list
     */
    int query(SegmentTreeNode *root, int start, int end)
    {
        if(root->start == start && root->end == end) return root->max;
        int mid = (root->start+root->end)/2;
        if(end <= mid) return query(root->left, start, end);
        if(start > mid) return query(root->right, start, end);
        if(mid < end) return min(query(root->left, start, mid), query(root->right, mid+1, end));
    }
    SegmentTreeNode *build(vector<int>&A, int start, int end)
    {
        if(start>end) return NULL;
        if(start == end) return new SegmentTreeNode(start, start, A[start]);
        int mid = (start+end)/2;
        SegmentTreeNode *left = build(A, start, mid);
        SegmentTreeNode *right = build(A, mid+1, end);
        SegmentTreeNode *node = new SegmentTreeNode(start, end, min(left->max, right->max));
    
        node->left = left;
        node->right = right;
        return node;
    }
    
    vector<int> intervalMinNumber(vector<int> &A, vector<Interval> &queries) {
        // write your code here
        vector<int> res;
    
        SegmentTreeNode *root = build(A, 0, A.size()-1);
        if(!root) return res;
        
        for(auto e:queries)
        {
            res.push_back(query(root,e.start, e.end));
        }
        return res;
    }
};

[LintCode] Segment Tree Modify

For a Maximum Segment Tree, which each node has an extra value max to store the maximum value in this node's interval.

Implement a modify function with three parameter root,index and value to change the node's value with [start, end] = [index, index] to the new given value. Make sure after this change, every node in segment tree still has the max attribute with the correct value.

Example

For segment tree:

                      [1, 4, max=3]
                    /                \
        [1, 2, max=2]                [3, 4, max=3]
       /              \             /             \
[1, 1, max=2], [2, 2, max=1], [3, 3, max=0], [4, 4, max=3]

if call modify(root, 2, 4), we can get:

                      [1, 4, max=4]
                    /                \
        [1, 2, max=4]                [3, 4, max=3]
       /              \             /             \
[1, 1, max=2], [2, 2, max=4], [3, 3, max=0], [4, 4, max=3]

or call modify(root, 4, 0), we can get:

                      [1, 4, max=2]
                    /                \
        [1, 2, max=2]                [3, 4, max=0]
       /              \             /             \
[1, 1, max=2], [2, 2, max=1], [3, 3, max=0], [4, 4, max=0]

/**
 * Definition of SegmentTreeNode:
 * class SegmentTreeNode {
 * public:
 *     int start, end, max;
 *     SegmentTreeNode *left, *right;
 *     SegmentTreeNode(int start, int end, int max) {
 *         this->start = start;
 *         this->end = end;
 *         this->max = max;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     *@param root, index, value: The root of segment tree and 
     *@ change the node's value with [index, index] to the new given value
     *@return: void
     */
    void modify(SegmentTreeNode *root, int index, int value) {
        // write your code here
        if(!root) return;
        if(root->start == root->end && root->start == index)
        {
            root->max = value;
            return;
        }
        if(root->start > index || root->end < index) return;
        
        if(index <= root->left->end) modify(root->left, index, value);
        else modify(root->right, index, value);
        root->max = max(root->left->max, root->right->max);
    }
};

[LintCode] Count of Smaller Number before itself

Give you an integer array (index from 0 to n-1, where n is the size of this array, value from 0 to 10000) . For each element Ai in the array, count the number of element before this element Ai is smaller than it and return count number array.

Example

For array [1,2,7,8,5], return [0,1,2,3,2]

Note

We suggest you finish problem Segment Tree Build, Segment Tree Query II and Count of Smaller Number before itself I first.

class Solution {
public:
      class SegmentTreeNode {
      public:
          int start, end, count;
          SegmentTreeNode *left, *right;
          SegmentTreeNode(int start, int end, int count) {
              this->start = start;
              this->end = end;
              this->count = count;
              this->left = this->right = NULL;
          }
      };

   /**
     * @param A: An integer array
     * @return: Count the number of element before this element 'ai' is 
     *          smaller than it and return count number array
     */
    SegmentTreeNode *buildLeft(int start, int end)
    {
        SegmentTreeNode *node = new SegmentTreeNode(start, end, 1);
        if(start == end) return node;
        node->left = new SegmentTreeNode(start, start, 1);
        node->right = new SegmentTreeNode(start+1, end, 0);
        return node;
    }
    
    int update(SegmentTreeNode *&node, int val)
    {
        if(val > node->end)
        {
            int res = node->count;
            SegmentTreeNode *head = new SegmentTreeNode(node->start, 
                                                 val, node->count+1);
            head->right = new SegmentTreeNode(node->end+1, val, 1);
            head->left = node;
            node = head;
            return res;
        }
        if(val < node->start)
        {
            SegmentTreeNode *head = new SegmentTreeNode(val, 
                              node->end, node->count+1);
            head->left = buildLeft(val, node->start-1);
            head->right = node;
            node = head;
            return 0;
        }
        node->count ++;
        if(node->left)
        {
            if(node->left->end >= val) return update(node->left, val);
            return update(node->right, val) + node->left->count;
        }
        else
        {
            node->left = new SegmentTreeNode(node->start, val, 1);
            node->right = new SegmentTreeNode(val+1, node->end, 
                                                   node->count);
        }
        return 0;
    }
    vector<int> countOfSmallerNumberII(vector<int> &A) {
        // write your code here
        int len = A.size();
        vector<int> res(len,0);
        if(0 == len)return res;
        SegmentTreeNode * root = new SegmentTreeNode(A[0], A[0], 1);
        for(int i=1;i<len;i++)
        {
            res[i] = update(root, A[i]);
        }
        return res;
    }
};

[LeetCode] Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

Recursive: Pre-order comparison

class Solution {
public:
    bool isSymmetric(TreeNode* left, TreeNode* right) {
        if(!left || !right) return left == right;
        return left->val == right->val && 
               isSymmetric(left->left, right->right) && 
               isSymmetric(left->right, right->left);
    }
    bool isSymmetric(TreeNode* root) {
        return isSymmetric(root, root);
    }
};

[LeetCode] Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

Analysis:
Note: the maximum path doesn't have to include the root. So, if we do DFS, we need to record the maximum path sum of a sub tree. For root->left, the DFS function should return the maximum path sum that ends at root->left, in order to connect to root. root->right should be the same.

class Solution {
public:
    int maxPathSum(int & maxSum, TreeNode* root) 
    {
        if(!root) return 0;
        int tmp = root->val;
        int left = maxPathSum(maxSum, root->left);
        if(left>0) tmp+=left;
        int right = maxPathSum(maxSum, root->right);
        if(right>0) tmp+=right;
        //Note: maxSum has already been compared with left and right
        //      in recursive calls
        maxSum = max(tmp, maxSum);
        return max(root->val, max(left, right) + root->val);
    }
    int maxPathSum(TreeNode* root) {
        if(!root) return 0;
        int maxSum = INT_MIN;
        int res = maxPathSum(maxSum, root);
        return max(res, maxSum);
    }
};

[LeetCode] Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the 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 {
public:
    TreeNode *buildTree(unordered_map<int, int> &map,
                        vector<int> &postorder,int ps, int pe, 
                        vector<int> &inorder, int is, int ie) 
    {
        if(ps>pe) return NULL;
        int i= map[postorder[pe]];
        TreeNode *node = new TreeNode(postorder[pe]);
        node->left = buildTree(map,postorder, ps, ps+i-is-1, inorder, is, i-1);
        node->right = buildTree(map,postorder, ps+i-is, pe-1, inorder, i+1, ie);
        return node;
    }

    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        unordered_map<int, int> map;
        for(int i=0;i<inorder.size();i++)
        {
            map[inorder[i]] = i;
        }
        int len = postorder.size();
        return buildTree(map, postorder, 0, len-1, inorder, 0, len-1);
    }
};

[LeetCode] Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

/**
 * 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 *buildTree(unordered_map<int, int> &map,
                        vector<int> &preorder,int ps, int pe, 
                        vector<int> &inorder, int is, int ie) 
    {
        if(ps>pe) return NULL;
        int i= map[preorder[ps]];
        TreeNode *node = new TreeNode(inorder[i]);
        node->left = buildTree(map,preorder, ps+1, ps+i-is, inorder, is, i-1);
        node->right = buildTree(map,preorder, ps+i-is+1, pe, inorder, i+1, ie);
        return node;
    }

    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        unordered_map<int, int> map;
        for(int i=0;i<inorder.size();i++)
        {
            map[inorder[i]] = i;
        }
        int len = preorder.size();
        return buildTree(map, preorder, 0, len-1, inorder, 0, len-1);
    }
};

[LeetCode] Course Schedule

The question can be found here: https://leetcode.com/problems/course-schedule/

Analysis:

You can just think of the problem checking if circle exists in a tree. Just need to note:
1) In a search path from any node,  if any node in the path appears more than once, there is a circle.
2) If a node is in a search path that doesn't have circle, any other searches should stop once they meet the node.
These will make the complexity O(n).
DFS solution:

See Course Schedule II

class Solution {
public:
    bool hasCircle(unordered_map<int, vector<int>> &map, 
                int cur, unordered_set<int>& visited)
    {
        if(!map.count(cur) || map[cur].size()==0) return false;
        //if cur course was visited, there is a circle
        if(visited.count(cur)) return true;
        visited.insert(cur);
        for(int i=0;i < map[cur].size();i++)
        {
            if(hasCircle(map, map[cur][i],visited)) return true;
        }  
        //the course cur is good, any other searches should not check it again.
        map[cur].clear();
        return false;
    }
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites)
    {
        unordered_map<int, vector<int> > map;
        unordered_set<int> visited;
        for(auto p:prerequisites) map[p[0]].push_back(p[1]);
        for(auto it:map)
        {
            if(hasCircle(map, it.first, visited)) return false;
            visited.clear();
        }
        return true;
    }
};

[LeetCode] Populating Next Right Pointers in Each Node II

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

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

/**
 * 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;
        queue<TreeLinkNode*> q;
        q.push(root);
        while(!q.empty())
        {
            TreeLinkNode * last = NULL;
            int size = q.size();
            for(int i=0;i<size;i++)
            {
                TreeLinkNode * curr = q.front();
                q.pop();
                if(last) last->next = curr;
                last = curr;
                if(curr->left) q.push(curr->left);
                if(curr->right) q.push(curr->right);
            }
        }
    }
};

[LeetCode] Populating Next Right Pointers in Each Node

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

/**
 * 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;
            connect(root->left);
        }
        if(root->right)
        {
            if(root->next)
            {
                root->right->next = root->next->left;
            }
            connect(root->right);
        }
    }
};