LeetCode 114 - Flatten Binary Tree to Linked List


Related: LeetCode 430 - Flatten a multilevel linked list
https://leetcode.com/problems/flatten-binary-tree-to-linked-list/
http://rangerway.com/way/algorithm-binary-tree-to-linked-list/
LeetCode – Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
1 / \ 2 5 / \ \ 3 4 6
The flattened tree should look like:
   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6
X.
http://bangbingsyb.blogspot.com/2014/11/leetcode-flatten-binary-tree-to-linked.html
从题目的例子马上发现其实就是preorder transverse整个tree，然后根据这个访问顺序，后访问到的节点成为先访问到的节点的右子节点。那么最不动脑的方法就是preorder transverse的时候把整个节点序列保存在一个vector中。最后再依次连起来。这个解法的空间复杂度包括了递归深度O(log n)和vector的空间O(n)，所以总的空间复杂度是O(n)。
    void flatten(TreeNode *root) {
        if(!root) return;
        vector<TreeNode*> allNodes;
        preorder(root, allNodes);
        int n = allNodes.size();
        for(int i=0; i<n-1; i++) {
            allNodes[i]->left = NULL;
            allNodes[i]->right = allNodes[i+1];
        }
        allNodes[n-1]->left = allNodes[n-1]->right = NULL;
    }
    
    void preorder(TreeNode *root, vector<TreeNode*> &allNodes) {
        if(!root) return;
        allNodes.push_back(root);
        preorder(root->left, allNodes);
        preorder(root->right, allNodes);
    }
X. Iterative
What is the time complexity of this solution? I wonder if it is O(nlogn) as we might traverse one root to leaf path per node to get the prenode.
http://buttercola.blogspot.com/2014/08/leetcode-flatten-binary-tree-to-linked.html
    public void flatten(TreeNode root){
        if (root == null) return;
        TreeNode p = root;
         
        while (p.left != null || p.right != null) {
            if (p.left != null) {
                TreeNode rChild = p.right;
                p.right = p.left;
                p.left = null;
                TreeNode rMost = p.right;
                while (rMost.right != null) {
                    rMost = rMost.right;
                }
                rMost.right = rChild;
            }
             
            p = p.right;
        }
    }
5) The final approach cost O(N) time and O(1) space: we directly simulate the process of finding the right most child of the left subtree! See the following code which is accepted:





1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16



void flatten(TreeNode *root) {
    TreeNode *rightMost = NULL;
    TreeNode *tmp = NULL;
    while (root) {
        if (root-&gt;left) {
            rightMost = root-&gt;left;
            while (rightMost-&gt;right)
                rightMost = rightMost-&gt;right;
            tmp = root-&gt;right;
            root-&gt;right = root-&gt;left;
            rightMost-&gt;right = tmp;
            root-&gt;left = NULL;
        }
        root = root-&gt;right;
    }
}
X. Left then right, Preorder traverse
https://longwayjade.wordpress.com/2015/04/23/leetcode-recursion-flatten-binary-tree-to-linked-list/
Use pre-oder traversal.
  • Define a field, recording the last visited element, so that we don’t lose track of the list when we update references. This field has to be out of the method.
  • Base case: if the current node is null, return;
  • Reduction: put the current node at lastvisit.right, and the current node becomes the new lastvisit node. Save the current.right node as savedRight, since it’s going to be changed in the next level of recursion. Then, call the method for current.left. After that, call the method for savedRight.
    public TreeNode lastvisit = null;
    public void flatten(TreeNode root) {
       if (root == null) return;
         TreeNode savedRight = root.right;  // have to save right, since right is going to be changed.
         if (lastvisit != null){
             lastvisit.left = null;
             lastvisit.right = root;
         }
         lastvisit = root;
         flatten(root.left);
         flatten(savedRight);
    }
https://www.sigmainfy.com/blog/leetcode-flatten-binary-tree-to-linked-list.html
We can solve this problem in a bottom up approach, that is, do a pre-order traversal, in a recursive way, we get the flatten list for each subtree, by getting the flattend list, we actually only need the head and the tail of that tree, then we append the head of the left list onto the root node, and append the head of the right list onto the tail of the left list. Just be careful when some of the list might be empty. This approach don’t need log N time to find the right most child. So the total time is linear O(N). And the space complexity would be O(h) where h is the height of the tree (i.e., the depth of the recursive calls)
http://bangbingsyb.blogspot.com/2014/11/leetcode-flatten-binary-tree-to-linked.html
假设某节点的左右子树T(root->left)和T(root->right)已经flatten成linked list了：

    1
  /    \
 2     5
  \       \
   3      6 <- rightTail
     \
      4  <- leftTail

如何将root、T(root->left)、T(root->right) flatten成一整个linked list？显而易见：

temp = root->right
root->right  = root->left
root->left = NULL
leftTail->right = temp

这里需要用到已经flatten的linked list的尾部元素leftTail, rightTail。所以递归返回值应该是生成的整个linked list的尾部。
需注意几个细节
ln 11：只有当左子树存在时才将它插入右子树中
ln 18-20：返回尾部元素时，需要特殊处理 (1) 有右子树的情况，(2) 无右子树但有左子树的情况，(3)左右子树均不存在的情况。
我感觉是在接的过程中是右子树接在了leftTail的下面，因此如果有右子树的话，最后的tail肯定是rightTail，如果没有右子树但是有左子树，tail肯定是leftTail


    void flatten(TreeNode *root) {
        TreeNode* rightTail = flattenBT(root);
    }
    
    TreeNode* flattenBT(TreeNode* root) {
        if(!root) return NULL;
        TreeNode *leftTail = flattenBT(root->left);
        TreeNode *rightTail = flattenBT(root->right);
        if(root->left) {
            TreeNode *temp = root->right;
            root->right = root->left;
            root->left = NULL;
            leftTail->right = temp;
        }
        
        if(rightTail) return rightTail;
        if(leftTail) return leftTail;
        return root;
    }

While the implementation in (1) does not explicitely search the right most child (tail of the flatten linked list). It could actually be done in an explicit way: For each node R, we append the left subtree of R into its right child, and append the right subtree of R onto the right most child of the left subtree of R, we basically follow a DFS order to do this and the tree will be flattened. Every time we need to find the right most subtree in a while loop but from an aggregate analysis, since for each node, the right child is set once, the final time complexity would still be O(N) and the space cost is O(h). 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

void flatten(TreeNode *root) {
    if (NULL == root)
        return ;

    TreeNode *rightChild = root-&gt;right;

    root-&gt;right = root-&gt;left;
    root-&gt;left = NULL;
    TreeNode *rightMost = root;

    while (rightMost-&gt;right)
        rightMost = rightMost-&gt;right;

    rightMost-&gt;right = rightChild;
    flatten(root-&gt;right);
}
3) Seems the code gets even more compact. There is another different implementation by using a previous pointer pointing to the previous node in the preorder traversal of the tree and the code actually is easier to understand and the time and space complexity is easier to derive although it is the same as with 2)





TreeNode *prev = NULL;
void flatten(TreeNode *root) {
    if (NULL == root)
        return;

    TreeNode *l = root-&gt;left;
    TreeNode *r = root-&gt;right;

    if (prev) {
        prev-&gt;right = root;
        prev-&gt;left = NULL;
    }

    prev = root;
    flatten(l);
    flatten(r);
}

4) Further improvement could be done by implementing the algorithm in iterative way. The easiest iterative implementation would be using an explicit stack, please see the “LeetCode Binary Tree Preorder Traversal: Iterative Using Stack” for further reference, and exact implementation could adopted. This approach still does not improve the space cost because the stack depth could still be h which is the height of the tree.
Remarks: Remember to set the left child of each node as NULL, otherwise, the OJ might report run time error
X. Right then left
http://fisherlei.blogspot.com/2012/12/leetcode-flatten-binary-tree-to-linked.html
1. Line 13~14
    刚开始的时候，首先flatten左树，然后处理右树。但是这样会导致处理右树的时候，节点的值已经在处理树的时候被破坏了。比如树为{1,2,3}，
     1
  /     \
2       3
如果先处理左树的话，当执行node->right = lhead的时候，右节点就已经被破坏了，node->right指向了2，而不是3。
1
   \
     2  (3)
当然，也可以用一个变量在处理左树前，保存右树地址。但是没必要，先处理右树就好了。
2. Line 22~23
    该循环是用于将p指针遍历到左树链表的最右节点。第一版时，这个循环是放在if语句以外，这就导致了，不必要的迭代了。比如当输入为{1,#,2}时，这个while循环会导致p指针遍历到右子树的最右节点，这显然是错的。
3. Line 20, 28
    不要忘了清空每一个指针，在新的链表中，左指针没必要保留。
1:  void flatten(TreeNode *root) {  
2:       // Start typing your C/C++ solution below  
3:       // DO NOT write int main() function  
4:       if(root == NULL)  
5:            return;  
6:       ConvertToLink(root);  
7:  }  
8:  TreeNode* ConvertToLink(TreeNode* node)  
9:  {  
10:       if(node->left == NULL && node->right == NULL)  
11:            return node;  
12:       TreeNode* rHead = NULL;  
13:       if(node->right != NULL)  
14:           rHead = ConvertToLink(node->right);               
15:       TreeNode* p = node;  
16:       if(node->left!=NULL)  
17:       {  
18:            TreeNode* lHead = ConvertToLink(node->left);   
19:            node->right = lHead;  
20:            lHead->left = NULL;  
21:            node->left = NULL;  
22:            while(p->right!=NULL)  
23:                 p = p->right;  
24:       }       
25:       if(rHead != NULL)  
26:       {  
27:            p->right = rHead;  
28:            rHead->left = NULL;  
29:       }  
30:       return node;  
31:  }
X. Post order traverse
https://www.jiuzhang.com/solutions/flatten-binary-tree-to-linked-list/


https://leetcode.com/problems/flatten-binary-tree-to-linked-list/discuss/36977/My-short-post-order-traversal-Java-solution-for-share
I would rename "prev" with "nxt" for the purpose of clarification
private TreeNode prev = null;

public void flatten(TreeNode root) {
    if (root == null)
        return;
    flatten(root.right);
    flatten(root.left);
    root.right = prev;
    root.left = null;
    prev = root;
}
    public void flatten(TreeNode root) {
        root = helper(root, null);
    }
    // helper function takes in the previous head, do the flattening and returns the head of the flatten binary tree
    private TreeNode helper(TreeNode root, TreeNode prev) {
        if (root == null) {
            return prev;
        }
        prev = helper(root.right, prev);
        prev = helper(root.left, prev);
        root.right = prev;
        root.left = null;
        prev = root;
        return root;
    }
X.
根据展开后形成的链表的顺序分析出是使用先序遍历，那么只要是数的遍历就有递归和非递归的两种方法来求解，这里我们也用两种方法来求解。首先来看递归版本的，思路是先利用DFS的思路找到最左子节点，然后回到其父节点，把其父节点和右子节点断开，将原左子结点连上父节点的右子节点上，然后再把原右子节点连到新右子节点的右子节点上，然后再回到上一父节点做相同操作

flatten left subtree
flatten right subtree
concatenate root -> left flatten subtree -> right flatten subtree
 public void flatten(TreeNode root) {
     if(root == null)
  return;
  
     flatten(root.left);
     flatten(root.right);
 
     // save current right for concatination
     TreeNode right = root.right;
 
     if(root.left != null) {
     
         // step 1: concatinate root with left flatten subtree
      root.right = root.left;
      root.left = null; // set left to null
  
      // step 2: move to the end of new added flatten subtree
      while(root.right != null)
       root = root.right;
   
      // step 3: contatinate left flatten subtree with flatten right subtree 
      root.right = right;
     }
 }
What's the time complexity? Is this O(nlogn)?
I think that each time when there is a "branch", we need to traverse the left chid of the root, which means that the time that every node will be visited depends on how many branches there are. Since there are logn branches at most, I think the worst case is O(nlogn).
We simply flatten left and right subtree and paste each sublist to the right child of the root. (don't forget to set left child to null)
public void flatten(TreeNode root) {
        if (root == null) return;
        
        TreeNode left = root.left;
        TreeNode right = root.right;
        
        root.left = null;
        
        flatten(left);
        flatten(right);
        
        root.right = left;
        TreeNode cur = root;
        while (cur.right != null) cur = cur.right;
        cur.right = right;
    }

Pre-Order Recursive Version:
维护先序遍历的前一个结点pre，然后每次把pre的左结点置空，右结点设为当前结点。这里需要注意的一个问题就是我们要先把右子结点保存一下，以便等会可以进行递归，否则有可能当前结点的右结点会被覆盖，后面就取不到了
http://rangerway.com/way/algorithm-binary-tree-to-linked-list/
http://www.jiuzhang.com/solutions/flatten-binary-tree-to-linked-list/
void flattenPreorder(TreeNode root, TreeNode[] prev) {
  if (root == null) return;
  TreeNode rightBranch = root.right;
  root.left = null;
  if (prev[0] != null) {
    prev[0].right = root;
  }
  prev[0] = root;
  flattenPreorder(root.left, prev);
  flattenPreorder(rightBranch, prev);
}
    private TreeNode lastNode = null;
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }

        if (lastNode != null) {
            lastNode.left = null;
            lastNode.right = root;
        }

        lastNode = root;
        TreeNode right = root.right;
        flatten(root.left);
        flatten(right);
    }
http://www.acmerblog.com/leetcode-solution-flatten-binary-tree-to-linked-list-6321.html
05    void flatten(TreeNode *root) {
06        if (root == nullptr) return;  // 终止条件
07
08        flatten(root->left);
09        flatten(root->right);
10
11        if (nullptr == root->left) return;
12
13        // 三方合并，将左子树所形成的链表插入到root和root->right之间
14        TreeNode *p = root->left;
15        while(p->right) p = p->right; //寻找左链表最后一个节点
16        p->right = root->right;
17        root->right = root->left;
18        root->left = nullptr;
19    }


X. Stack Pre-Oder traversal:
Go down through the left, when right is not null, push right to stack.
public void flatten(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode p = root;
 
        while(p != null || !stack.empty()){
            if(p.right != null){
                stack.push(p.right);
            }
 
            if(p.left != null){
                p.right = p.left;
                p.left = null;
            }else if(!stack.empty()){
                TreeNode temp = stack.pop();
                p.right=temp;
            }
 
            p = p.right;
        }
    }
http://gongxuns.blogspot.com/2012/12/leetcode-flatten-binary-tree-to-linked.html
DFS prev pointer.
    public void flatten(TreeNode root) {
        Stack<TreeNode> toVisit = new Stack<TreeNode>();
        if(root==null) return;
        toVisit.push(root);
        TreeNode prev = null;
        while(!toVisit.isEmpty()){
            TreeNode cur = toVisit.pop();
            if(cur.right!=null)
                toVisit.push(cur.right);
            if(cur.left!=null)
                toVisit.push(cur.left);
            if(prev!=null){
                prev.left=null;
                prev.right = cur;
            }
            prev=cur;
        }
http://yucoding.blogspot.com/2013/01/leetcode-question-30-flatten-binary.html
O(nlogn)
The flatten procedure is like:  cut the left child and set to right, the right child is then linked to somewhere behind the left child. Where should it be then?  Actually the right child should be linked to the most-right node of the left node. So the algorithm is as follows:
(1) store the right child (we call R)
(2) find the right-most node of left child
(3) set R as the right-most node's right child.
(4) set left child as the right child
(5) set the left child NULL
(6) set current node to current node's right child.
(7) iterate these steps until all node are flattened.
    void flatten(TreeNode *root) {
        while (root){
            if (root->left){
                TreeNode* pre=root->left;
                while (pre->right){pre = pre->right;}
                pre->right = root->right;
                root->right = root->left;
                root->left = NULL;
            }
            root=root->right;
        }
    }
对root的左子树进行处理，将左子树的根节点和左子树的右子树插入右子树中
接下来对节点2进行处理，同样将2的左子树插入右子树中
public void flatten(TreeNode root) {
 4         if(root == null){
 5             return;
 6         }
 8         if(root.left != null){
 9             TreeNode rightNode = root.right;
10             TreeNode leftNode = root.left;
11             root.left = null;
12             root.right = leftNode;
13             TreeNode p = leftNode;
14             while(p.right != null){
15                 p = p.right;
16             }
17             p.right = rightNode;
18         }
19         flatten(root.right);
20     }


http://blog.csdn.net/perfect8886/article/details/20000083
         1
          \
           2
          / \
         3   4
              \
               5
                \
                 6


还有种非递归的写法，没有借助栈就实现了按先序遍历顺序展平，在构造过程中，只要树中有多出来的分叉（左子树），就嫁接到根节点和右子树之间，具体参见解法2。
    


  1.     public void flatten(TreeNode root) {  
    2. 



  2.         while (root != null) {  
    3. 



  3.             if (root.left != null) {  
    4. 



  4.                 TreeNode p = root.left;  
    5. 



  5.                 while (p.right != null) {  
    6. 



  6.                     p = p.right;  
    7. 



  7.                 }  
    8. 



  8.                 p.right = root.right;  
    9. 



  9.                 root.right = root.left;  
    10. 



  10.                 root.left = null;  
    11. 



  11.             }  
    12. 



  12.             root = root.right;  
    13. 



  13.         }  
    14. 



  14.     }  
    15.
http://codesays.com/2014/solution-to-flatten-binary-tree-to-linked-list-by-leetcode/
http://rangerway.com/way/algorithm-binary-tree-to-linked-list/
http://fisherlei.blogspot.com/2012/12/leetcode-flatten-binary-tree-to-linked.html
Inorder version
TreeNode flattenInorder(TreeNode root) {
  TreeNode[] prev = new TreeNode[1];
  TreeNode[] head = new TreeNode[1];
  flattenInorder(root, prev, head);
  return head[0];
}
void flattenInorder(TreeNode root, TreeNode[] prev, TreeNode[] head) {
  if (root == null) return;
  flattenInorder(root.left, prev, head);
  root.left = null;
  if (prev[0] != null) {
    prev[0].right = root;
  }
  prev[0] = root;
  if (head[0] == null) {
    head[0] = root;
  }
  flattenInorder(root.right, prev, head);
}
PreOder
  • As the root of BT is the head of LL, we do not need to set head pointer.
  • As the right pointer of each node will be set before recusion called on rightBranch, so we need to set a variable to mark rightBranch in every recursion.
void flattenPreorder(TreeNode root, TreeNode[] prev) {
  if (root == null) return;
  TreeNode rightBranch = root.right;
  root.left = null;
  if (prev[0] != null) {
    prev[0].right = root;
  }
  prev[0] = root;
  flattenPreorder(root.left, prev);
  flattenPreorder(rightBranch, prev);
}
Post-Order to List.
void flattenPostorder(TreeNode root, TreeNode[] prev, TreeNode[] head) {
    if (root == null) return;
    flattenPostorder(root.left, prev, head);
    if (head[0] == null) {
      head[0] = root;
    }
    flattenPostorder(root.right, prev, head);
    root.left = null;
    root.right = null;
    if (prev[0] != null) {
      prev[0].right = root;
    }
    prev[0] = root;
  }
The iteration traverse of Binary Tree is commonly implemented with an assistant Stack. But in this quesiton, we are required to use constant space, so we should take advantage of the left/right pointers.
Pre-Order
void flattenInorder(TreeNode root) {
  while (root != null) {
    if (root.left != null) {
      TreeNode prev = root.left;
      while (prev.right != null) {
        prev = prev.right;
      }
      prev.right = root.right;
      root.right = root.left;
      root.left = null;
    }
    root = root.right;
  }

}
TreeNode flattenInorder(TreeNode root) {
  TreeNode head = null;
  TreeNode last = null;
  while (root != null) {
    if (root.left != null) {
      TreeNode pre = root.left;
      while (pre.right != null) {
        pre = pre.right;
      }
      pre.right = root;
      pre = pre.right;
      root = root.left;
      pre.left = null;
      if (last != null) {
        last.right = root;
      }
    } else {
      if (head == null) head = root;
      last = root;
      root = root.right;
    }
  }
  return head;

}

此题还可以延伸到用中序，后序，层序的遍历顺序来展开原二叉树，分别又有其对应的递归和非递归的方法，有兴趣的童鞋可以自行实现
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
  • 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...
  • Greedy Algorithms | Set 3 (Huffman Coding) | GeeksforGeeks
    Greedy Algorithms | Set 3 (Huffman Coding) | GeeksforGeeks Huffman coding is a lossless data compression algorithm. The idea is to assign ...
  • 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...
  • Minimum area of a square enclosing given set of points
    Problem solving with programming: Minimum area of a square enclosing given set of points Given a set of coordinates in a two dimensional ...
  • HackerRank: N Puzzle
    HackerRank: N Puzzle N Puzzle is a sliding blocks game that takes place on a k * k grid with ((k * k) - 1) tiles each numbered from 1 to ...
  • LeetCode 394 - Decode String
    Follow up:  LeetCode 471 - Encode String with Shortest Length https://leetcode.com/problems/decode-string/ Given an encoded string, retu...
  • Hilbert Curve - Airbnb
    airbnb面试题汇总 Hilbert Curve Hilbert曲线可以无限阶下去，从1阶开始，落在一个矩阵里，让你写个function，三个参数（x,y,阶数），return 这个点（x,y）是在这阶curve里从原点出发的第几步 int hilbertCurve(...
  • Simple Text Editor - HackerRank
    https://www.hackerrank.com/challenges/simple-text-editor In this problem, your task is to implement a simple text editor. Initially, a fi...
  • LeetCode 291 - Word Pattern II
    leetcode 291 Word Pattern II Given a  pattern  and a string  str , find if  str  follows the same pattern. Here  follow  means a full m...