LeetCode 222 - Count Complete Tree Nodes


[LeetCode]Count Complete Tree Nodes | 书影博客
Given a complete binary tree, count the number of nodes.
Note:
Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
Example:
Input: 
    1
   / \
  2   3
 / \  /
4  5 6

Output: 6

https://blog.csdn.net/jmspan/article/details/51056085
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        int leftmost = 0;
        TreeNode left = root;
        while (left != null) {
            leftmost ++;
            left = left.left;
        }
        int rightmost = 0;
        TreeNode right = root;
        while (right != null) {
            rightmost ++;
            right = right.right;
        }
        if (leftmost == rightmost) return (int)Math.pow(2, leftmost)-1;
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}
假设最坏情况下总有一颗子树不是完美二叉树，这样从根节点开始，检查左右子树深度需要2h时间（h为深度），而对于根节点下面的一颗子树，检查深度需要2(h-1)时间，因此总体的时间复杂度为O(2h+2(h-1)+2(h-2)+...+2*1)=O(h^2)。
但是提交发现还是Time Limit Exceeded，这是为什么呢？原来是Math.pow函数坑爹啊，把它改为移位运算，立马accept：
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        int leftmost = 0;
        TreeNode left = root;
        while (left != null) {
            leftmost ++;
            left = left.left;
        }
        int rightmost = 0;
        TreeNode right = root;
        while (right != null) {
            rightmost ++;
            right = right.right;
        }
        if (leftmost == rightmost) return (1<<leftmost)-1;
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
但成绩并不理想：
还有什么提升的地方吗？分析上面程序发现，递归统计子树的时候，leftmost和rightmost被重复统计多次，这是没有必要的，这就有点动态规划的思想了，有子问题重叠，例如左子树的leftmost值应等于根节点leftmost-1，右子树同理，所以按照动态规划思想改进一下，得到了方法三。


方法三：动态规划思想的完全二叉树递归统计

考虑到统计最左节点深度和最有节点深度有子问题重叠，所以可以避免此部分重复计算：




解法II：递归: Time complexity is O(h^2) - O(log(n)^2)
http://www.cnblogs.com/grandyang/p/4567827.html
A Complete Binary Tree （CBT) is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
对于一颗二叉树，假设其深度为d（d>1）。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树；
换句话说，完全二叉树从根结点到倒数第二层满足完美二叉树，最后一层可以不完全填充，其叶子结点都靠左对齐。
A Perfect Binary Tree(PBT) is a tree with all leaf nodes at the same depth. All internal nodes have degree 2.
二叉树的第i层至多拥有2^{i-1}个节点数；深度为k的二叉树至多总共有{\displaystyle 2^{\begin{aligned}k+1\end{aligned}}-1}个节点数，而总计拥有节点数匹配的，称为“满二叉树”；
A Full Binary Tree (FBT) is a tree in which every node other than the leaves has two children.
换句话说，所有非叶子结点的度都是2。（只要你有孩子，你就必然是有两个孩子。）
通过上面的定义，我们可以看出二者的关系是，完美二叉树一定是完全二叉树，而完全二叉树不一定是完美二叉树。那么这道题给的完全二叉树就有可能是完美二叉树，若是完美二叉树，节点个数很好求，为2的h次方-1，h为该完美二叉树的高度。这道题可以用递归和非递归两种方法来解。我们先来看递归的方法，思路是分别找出以当前节点为根节点的左子树和右子树的高度并对比，如果相等，则说明是满二叉树，直接返回节点个数，如果不相等，则节点个数为左子树的节点个数加上右子树的节点个数再加1(根节点)，其中左右子树节点个数的计算可以使用递归来计算

O(N^2)
    int countNodes(TreeNode* root) {
        int hLeft = 0, hRight = 0;
        TreeNode *pLeft = root, *pRight = root;
        while (pLeft) {
            ++hLeft;
            pLeft = pLeft->left;
        }
        while (pRight) {
            ++hRight;
            pRight = pRight->right;
        }
        if (hLeft == hRight) return pow(2, hLeft) - 1;
        return countNodes(root->left) + countNodes(root->right) + 1;
    }


    int countNodes(TreeNode* root) {
        int hLeft = leftHeight(root);
        int hRight = rightHeight(root);
        if (hLeft == hRight) return pow(2, hLeft) - 1;
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
    int leftHeight(TreeNode* root) {
        if (!root) return 0;
        return 1 + leftHeight(root->left);
    }
    int rightHeight(TreeNode* root) {
        if (!root) return 0;
        return 1 + rightHeight(root->right);
    }

 https://leetcode.com/problems/count-complete-tree-nodes/discuss/61948/accepted-easy-understand-java-solutionf
This is a clean and smart solution, my understanding is as follows:
  1. A fully completed tree has node number: count = 2 ^ depth - 1
    for example: [1,2,3]
    depth is 2
    count = 2 ^ 2 - 1 = 3
  2. Compare left height and right height, if equal, use the formular, otherwise recurvisely search left and right at next level
  3. The search pattern is very similar to binary search, the difference of heights ethier exsits in left side, or right side
  4. Due to the reason stated in point 3, the time complexity is h ^ 2, there is h times for each level, and h times for calculating height at each level

https://discuss.leetcode.com/topic/15533/concise-java-solutions-o-log-n-2
https://leetcode.com/discuss/38899/easy-short-c-recursive-solution
Let n be the total number of the tree. It is likely that you will get a child tree as a perfect binary tree and a non-perfect binary tree (T(n/2)) at each level.
T(n) = T(n/2) + c1 lgn
       = T(n/4) + c1 lgn + c2 (lgn - 1)
       = ...
       = T(1) + c [lgn + (lgn-1) + (lgn-2) + ... + 1]
       = O(lgn*lgn)  
    int height(TreeNode root) {
        return root == null ? -1 : 1 + height(root.left);
    }
    public int countNodes(TreeNode root) {
        int h = height(root);
        return h < 0 ? 0 :
               height(root.right) == h-1 ? (1 << h) + countNodes(root.right)
                                         : (1 << h-1) + countNodes(root.left);
    }
Explanation
The height of a tree can be found by just going left. Let a single node tree have height 0. Find the height h of the whole tree. If the whole tree is empty, i.e., has height -1, there are 0 nodes.
Otherwise check whether the height of the right subtree is just one less than that of the whole tree, meaning left and right subtree have the same height.
  • If yes, then the last node on the last tree row is in the right subtree and the left subtree is a full tree of height h-1. So we take the 2^h-1 nodes of the left subtree plus the 1 root node plus recursively the number of nodes in the right subtree.
  • If no, then the last node on the last tree row is in the left subtree and the right subtree is a full tree of height h-2. So we take the 2^(h-1)-1 nodes of the right subtree plus the 1 root node plus recursively the number of nodes in the left subtree.
Since I halve the tree in every recursive step, I have O(log(n)) steps. Finding a height costs O(log(n)). So overall O(log(n)^2).
Here's an iterative version as well, with the benefit that I don't recompute h in every step.

    int height(TreeNode root) {
        return root == null ? -1 : 1 + height(root.left);
    }
    public int countNodes(TreeNode root) {
        int nodes = 0, h = height(root);
        while (root != null) {
            if (height(root.right) == h - 1) {
                nodes += 1 << h;
                root = root.right;
            } else {
                nodes += 1 << h-1;
                root = root.left;
            }
            h--;
        }
        return nodes;
    }
https://discuss.leetcode.com/topic/31457/a-very-clear-recursive-solution-isn-t-it
https://discuss.leetcode.com/topic/18508/accepted-clean-java-solution/2
  public int countNodes(TreeNode root) {
    if (root == null)
      return 0;
            
    int hLeft = getHeight(root.left);
    int hRight = getHeight(root.right);
        
    if (hLeft == hRight)
      return (1 << hLeft) + countNodes(root.right);
    else
      return (1 << hRight) + countNodes(root.left);
    
  }
    
  int getHeight(TreeNode root) {
    if (root == null)
      return 0;
        
    return 1 + getHeight(root.left);
  }
https://discuss.leetcode.com/topic/15525/concise-java-iterative-solution-o-logn-2

 private int getHeight(TreeNode root, UnaryOperator<TreeNode> nextNode) {
  return root==null?0:1+getHeight(nextNode.apply(root),nextNode);
 }
X. 
https://discuss.leetcode.com/topic/21317/accepted-easy-understand-java-solution/
Two cases:
  1. when it's a full binary tree, will be the easiest case: just return (1 << leftHeight) -1
  2. when it's not full binary tree we'll calculate its left and right subtree nodes recursively and then plus one (root node).
One more comment: I'd like to add one more line:
if(root == null) return 0;
at the beginning of your countNodes(TreeNode root) function, it at least helps me understand it better, basically, that line serves as the base case when the countNodes() function exits. Otherwise, it's not super clear to me when countNodes() reaches null, how it's going to return.
public int countNodes(TreeNode root) {

    int leftDepth = leftDepth(root);
 int rightDepth = rightDepth(root);

 if (leftDepth == rightDepth)
  return (1 << leftDepth) - 1;
 else
  return 1+countNodes(root.left) + countNodes(root.right);

}

private int rightDepth(TreeNode root) {
 // TODO Auto-generated method stub
 int dep = 0;
 while (root != null) {
  root = root.right;
  dep++;
 }
 return dep;
}

private int leftDepth(TreeNode root) {
 // TODO Auto-generated method stub
 int dep = 0;
 while (root != null) {
  root = root.left;
  dep++;
 }
 return dep;
}

A Different Solution - 544 ms
class Solution {
    public int countNodes(TreeNode root) {
        if (root == null)
            return 0;
        TreeNode left = root, right = root;
        int height = 0;
        while (right != null) {
            left = left.left;
            right = right.right;
            height++;
        }
        if (left == null)
            return (1 << height) - 1;
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}
Note that that's basically this:
public int countNodes(TreeNode root) {
    if (root == null)
        return 0;
    return 1 + countNodes(root.left) + countNodes(root.right)

That would be O(n). But... the actual solution has a gigantic optimization. It first walks all the way left and right to determine the height and whether it's a full tree, meaning the last row is full. If so, then the answer is just 2^height-1. And since always at least one of the two recursive calls is such a full tree, at least one of the two calls immediately stops. Again we have runtime O(log(n)^2).
the recurrence relation can be expressed as T(n) = 1 * T(n/ 2) + log(n).
log(n) is not Ω(nc) for c>0, as you can see here. You need to use case 2.
如果当前子树的“极左节点”（从根节点出发一路向左）与“极右节点”（从根节点出发一路向右）的高度h相同，则当前子树为满二叉树，返回2^h - 1
否则，递归计算左子树与右子树的节点个数。
https://leetcode.com/discuss/38899/easy-short-c-recursive-solution
int countNodes(TreeNode* root) { if (!root) return 0; int hl = 0, hr = 0; TreeNode *l = root, *r = root; while(l) {hl++; l = l->left;} while(r) {hr++; r = r->right;} if (hl == hr) return pow(2, hl) - 1; return 1 + countNodes(root->left) + countNodes(root->right); }
http://www.programcreek.com/2014/06/leetcode-count-complete-tree-nodes-java/
1) get the height of left-most part
2) get the height of right-most part
3) when they are equal, the # of nodes = 2^h -1
4) when they are not equal, recursively get # of nodes from left&right sub-trees
count-complete-tree-nodes
count-complete-tree-nodes-2
Time complexity is O(h^2).
public int countNodes(TreeNode root) {
    if(root==null)
        return 0;
 
    int left = getLeftHeight(root)+1;    
    int right = getRightHeight(root)+1;
 
    if(left==right){
        return (2<<(left-1))-1;
    }else{
        return countNodes(root.left)+countNodes(root.right)+1;
    }
}
 
public int getLeftHeight(TreeNode n){
    if(n==null) return 0;
 
    int height=0;
    while(n.left!=null){
        height++;
        n = n.left;
    }
    return height;
}
 
public int getRightHeight(TreeNode n){
    if(n==null) return 0;
 
    int height=0;
    while(n.right!=null){
        height++;
        n = n.right;
    }
    return height;
}
http://segmentfault.com/a/1190000003818177
X. 递归树高法
完全二叉树的一个性质是，如果左子树最左边的深度，等于右子树最右边的深度，说明这个二叉树是满的，即最后一层也是满的，则以该节点为根的树其节点一共有2^h-1个。如果不等于，则是左子树的节点数，加上右子树的节点数，加上自身这一个。

这里在左节点递归时代入了上次计算的左子树最左深度减1，右节点递归的时候代入了上次计算的右子树最右深度减1，可以避免重复计算这些深度
做2的幂时不要用Math.pow，这样会超时。用1<<height这个方法来得到2的幂
    public int countNodes(TreeNode root) {
        return countNodes(root, -1, -1);
    }
    
    private int countNodes(TreeNode root, int lheight, int rheight){
        // 如果没有上轮计算好的左子树深度，计算其深度
        if(lheight == -1){
            lheight = 0;
            TreeNode curr = root;
            while(curr != null){
                lheight++;
                curr = curr.left;
            }
        }
        // 如果没有上轮计算好的右子树深度，计算其深度
        if(rheight == -1){
            rheight = 0;
            TreeNode curr = root;
            while(curr != null){
                rheight++;
                curr = curr.right;
            }
        }
        // 如果两个深度一样，返回2^h-1
        if(lheight == rheight) return (1 << lheight) - 1;
        // 否则返回左子树右子树节点和加1
        return 1 + countNodes(root.left, lheight - 1, -1) + countNodes(root.right, -1, rheight - 1);
    }
用迭代法的思路稍微有点不同，因为不再是递归中那样的分治法，我们迭代只有一条正确的前进方向。所以，我们判断的时左节点的最左边的深度，和右节点的最左边深度。因为最后一层结束的地方肯定在靠左的那侧，所以我们要找的就是这个结束点。如果两个深度相同，说明左子树和右子树都是满，结束点在右侧，如果右子树算出的最左深度要小一点，说明结束点在左边，右边已经是残缺的了。根据这个大小关系，我们可以确定每一层的走向，最后找到结束点。另外，还要累加每一层的节点数，最后如果找到结束点，如果结束点是左节点，就多加1个，如果结束点是右节点，就多加2个。

注意

同样的，记录上次计算的最左深度，可以减少一些重复计算
用int记录上次最左深度更快，用Integer则会超时
public class Solution {
    public int countNodes(TreeNode root) {
        int res = 0;
        Integer lheight = null, rheight = null;
        while(root != null){
            // 得到左节点的最左深度
            int leftH = getH(root.left);
            // 得到右节点的最左深度
            int rightH = getH(root.right);
            // 左节点的最左深度大，说明右边已经残缺，结束点在左边
            if(leftH > rightH){
                if(rightH != 0) res += 1 << rightH;
                else return res + 2;
                root = root.left;
            // 否则说明结束点在右边
            } else {
                if(leftH != 0) res += 1 << leftH;
                else return res + 1;
                root = root.right;
            }
        }
        return res;
    }
    
    private int getH(TreeNode root){
        int h = 0;
        while(root != null){
            ++h;
            root = root.left;
        }
        return h;
    }
}

public class Solution {
    public int countNodes(TreeNode root) {
        int res = 0;
        int lheight = -1, rheight = -1;
        while(root != null){
            // 如果没有上次记录的左边最左深度，重新计算
            if(lheight == -1){
                TreeNode curr = root.left;
                lheight = 0;
                while(curr != null){
                    curr = curr.left;
                    lheight++;
                }    
            }
            // 如果没有上次记录的右边最左深度，重新计算
            if(rheight == -1){
                TreeNode curr = root.right;
                rheight = 0;
                while(curr != null){
                    curr = curr.left;
                    rheight++;
                }
            }
            // 深度相同，说明结束点在右边
            if(lheight == rheight){
                // 如果是不是最后一个节点，累加这一层的节点
                if(lheight != 0){
                    res += 1 << lheight;
                } else {
                // 如果是最后一个节点，结束点在右边意味着右节点是缺失的，返回res+1
                    return res + 1;
                }
                root = root.right;
                lheight = rheight - 1;
                rheight = -1;
            // 否则结束点在左边
            } else {
                // 如果是不是最后一个节点，累加这一层的节点
                if(rheight != 0){
                    res += 1 << rheight;
                } else{
                // 如果是最后一个节点，返回res+2
                    return res + 2;
                }
                root = root.left;
                lheight = lheight - 1;
                rheight = -1;
            }
        }
        return res;
    }
}
http://shibaili.blogspot.com/2015/06/day-112-count-complete-tree-nodes.html
iterative
检查右子树是不是perfect tree，如果是，则缺口在左子树，此时加上右边的个数。
如果不是，则缺口在右子树，此时加上左边的个数
此题关键在于对高度的判断，然后对树的分解
    int getHeight(TreeNode *root) {
        int height = 0;
        while (root != NULL) {
            height++;
            root = root->left;
        }
         
        return height;
    }
    int countNodes(TreeNode* root) {
        int height = getHeight(root);
        int count = 0;
        while (root != NULL) {
            if (getHeight(root->right) == height - 1) {
                count += 1 << height - 1;
                root = root->right;
            }else {
                count += 1 << height - 2;
                root = root->left;
            }
             
            height--;
        }
         
        return count;
    }
解法I：二分枚举
https://discuss.leetcode.com/topic/31392/my-java-solution-with-explanation-which-beats-99/2
Basically my solution contains 2 steps.
(1) Firstly, we need to find the height of the binary tree and count the nodes above the last level.
(2) Then we should find a way to count the nodes on the last level.
Here I used a kind of binary search. We define the "midNode" of the last level as a node following the path "root->left->right->right->...->last level".
If midNode is null, then it means we should count the nodes on the last level in the left subtree.
If midNode is not null, then we add half of the last level nodes to our result and then count the nodes on the last level in the right subtree.
Of course I used some stop condition to make the code more efficient, e.g. when a tree has height 1, it means it only has 3 cases: 1. has right son; 2. only has left son; 3. has no son.
public int countNodes(TreeNode root) {
 if (root==null) return 0;
 if (root.left==null) return 1;
 int height = 0;
    int nodesSum = 0;
 TreeNode curr = root;
    while(curr.left!=null) {
     nodesSum += (1<<height);
     height++;
     curr = curr.left;
    }
    return nodesSum + countLastLevel(root, height);
}

private int countLastLevel(TreeNode root, int height) {
 if(height==1) 
  if (root.right!=null) return 2;
  else if (root.left!=null) return 1;
  else return 0;
 TreeNode midNode = root.left;
 int currHeight = 1;
 while(currHeight<height) {
  currHeight++;
  midNode = midNode.right;
 }
 if (midNode==null) return countLastLevel(root.left, height-1);
 else return (1<<(height-1)) + countLastLevel(root.right, height-1);
}
高度为h的完全二叉树，其节点个数等于高度为h-1的满二叉树的节点个数 + 最后一层的节点个数。
因此，只需要二分枚举第h层的节点个数即可。
例如高度为2，包含6个节点的完全二叉树：
Lv0        1 
         /    \
Lv1     2      3
       /  \   /  \
Lv2   4   5  6   -

No.   00  01 10
http://www.cnblogs.com/easonliu/p/4556487.html
假设最后一层在 h 层，那么一共有 2^(h-1) 个结点，一共需要 h - 1 位来编号，从根结点出发，向左子树走编号为 0， 向右子树走编号为 1，那么最后一层的编号正好从0 ~ 2^(h-1) - 1。复杂度为 O(h*log(2^(h-1))) = O(h^2)
int countNodes(TreeNode* root) { int depth = 0; TreeNode* node = root; while (node) { depth++; node = node->left; } if (depth == 0) { return 0; } int left = 0, right = (1 << (depth - 1)) - 1; while (left <= right) { int mid = (left + right) >> 1; if (getNode(root, mid, depth - 1)) { left = mid + 1; } else { right = mid - 1; } } return (1 << (depth - 1)) + right; } TreeNode* getNode(TreeNode* root, int path, int depth) { while (depth-- && root) { if (path & (1 << depth)) { root = root->right; } else { root = root->left; } } return root; }
12     bool isOK(TreeNode *root, int h, int v) {
13         TreeNode *p = root;
14         for (int i = h - 2; i >= 0; --i) {
15             if (v & (1 << i)) p = p->right;
16             else p = p->left;
17         }
18         return p != NULL;
19     }
20     
21     int countNodes(TreeNode* root) {
22         if (root == NULL) return 0;
23         TreeNode *p = root;
24         int h = 0;
25         while (p != NULL) {
26             p = p->left;
27             ++h;
28         }
29         int l = 0, r = (1 << (h - 1)) - 1, m;
30         while (l <= r) {
31             m = l + ((r - l) >> 1);
32             if (isOK(root, h, m)) l = m + 1;
33             else r = m - 1;
34         }
35         return (1 << (h - 1)) + r;
36     }
http://techinpad.blogspot.com/2015/06/leetcode-count-complete-tree-nodes.html
 Analysis: We just need find where the node stops at the lowest level. To achieve that, we need to compare the depth of the node on the left or the right side of the contour. 
Don't understand it.
  1.     int countNodes(int depth, TreeNode *root)  
  2.     {  
  3.         if(!root) return 0;  
  4.         int res = 0;  
  5.         int level = 1;  
  6.         TreeNode* p = root->left;  
  7.         for(;p;p = p->right) level ++;  
  8.           
  9.         if(level == depth)   
  10.         {  
  11.             res = pow(2, depth-1) + countNodes(depth-1, root->right);  
  12.         }  
  13.         else  
  14.         {  
  15.             res = pow(2, depth-2) + countNodes(depth-1,  root->left);  
  16.         }  
  17.         return res;  
  18.     }  
  19.     int countNodes(TreeNode* root) {  
  20.         if(!root) return 0;  
  21.         TreeNode *p = root;  
  22.         int depth = 0;  
  23.         while(p)  
  24.         {  
  25.             depth ++;  
  26.             p = p->left;  
  27.         }  
  28.         return countNodes(depth, root);  
  29.     }  
http://blog.csdn.net/u012925008/article/details/46398141
https://discuss.leetcode.com/topic/15533/concise-java-solutions-o-log-n-2
Here's one based on victorlee's C++ solution.
class Solution {
    public int countNodes(TreeNode root) {
        if (root == null)
            return 0;
        TreeNode left = root, right = root;
        int height = 0;
        while (right != null) {
            left = left.left;
            right = right.right;
            height++;
        }
        if (left == null)
            return (1 << height) - 1;
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}
Note that that's basically this:
public int countNodes(TreeNode root) {
    if (root == null)
        return 0;
    return 1 + countNodes(root.left) + countNodes(root.right)
That would be O(n). But... the actual solution has a gigantic optimization. It first walks all the way left and right to determine the height and whether it's a full tree, meaning the last row is full. If so, then the answer is just 2^height-1. And since always at least one of the two recursive calls is such a full tree, at least one of the two calls immediately stops. Again we have runtime O(log(n)^2).
Read full article from [LeetCode]Count Complete Tree Nodes | 书影博客
at
Labels: , , , , , , , , ,

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts

  • Archives
  • HackerRank: Pacman A*
    HackerRank: Pacman A* In the previous game, you performed UCS on the PacMan grid. In this game we use AStar algorithm to reduce the nodes...
  • LeetCode 471 - Encode String with Shortest Length
    Related:  LeetCode 394 - Decode String http://bookshadow.com/weblog/2016/12/11/leetcode-encode-string-with-shortest-length/ Given a  non...
  • HackerRank: PacMan - BFS
    HackerRank: PacMan - BFS In the previous game, you performed DFS on the PacMan grid. It was seen that DFS might not always give the short...
  • DropBox Interview Misc
    https://paper.dropbox.com/doc/Interview-Notes-Dropbox-wl7npLjRBjrAKA5AOBsaM Behavioural https://www.paysa.com/blog/2017/04/05/what-to...
  • Buttercola: Buddy System
    Buttercola: Buddy System Given a complete binary tree with nodes of values of either 1 or 0, the following rules always hold: 1. A node...
  • Print all sequences of given length | GeeksforGeeks
    Print all sequences of given length | GeeksforGeeks Given two integers k and n, write a function that prints all the sequences of length k...
  • LeetCode 988 - Smallest String Starting From Leaf
    https://leetcode.com/problems/smallest-string-starting-from-leaf/ Given the  root  of a binary tree, each node has a value from  0  to  2...
  • LeetCode 860 - Lemonade Change
    https://leetcode.com/problems/lemonade-change/description/ At a lemonade stand, each lemonade costs  $5 .  Customers are standing in a ...
  • Uber Interview
    优步面经 Email domain address typo, need to figure out and return correct domain name. e.g. yhaoo–> yahoo, giaml –> gmail, hmailot–> ...