Leetcode: Recover binary search tree

August 31, 2015

   想写点什么, 因为这道题花了我好几个小时, 在周日, 除了在球场上跑了二个小时, 就泡在这道题上面.

read blogs: http://www.lifeincode.net/programming/leetcode-recover-binary-search-tree-java/ http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html C# implementations: 没有明白算法, 写了一个C#版本, 从读代码, 看有哪些不明白的地方. https://github.com/jianminchen/Leetcode_C-/blob/master/99RecoverBinarySearchTree.cs 简易递归版本, 但是, 找二个违例点不是很到位.  https://github.com/jianminchen/Leetcode_C-/blob/master/99RecoverBinarySearchTreeB.cs 总算明白, 开始写几个小函数, 看能不能记住, 容易维护, 测试案例是不是很清楚. 比较满意的代码. 看看注释, 几个月过后, 希望能几分钟内回忆起算法.  明白了算法, 再把代码写清楚, 让错误无处可藏. work on extracting small functions, and then, understand the algorithm better. No place for a bug.  https://github.com/jianminchen/Leetcode_C-/blob/master/99RecoveryBinarySearchTree_C.cs 有空周末在黑板上讲讲这道题, 练习自己的表达能力, 做一个小录像, 放在网上.

Reading time for algorithm, web programming

August 29, 2015

阅读是最好的放松方式, 当然, 运动, 网球是更好的放松方法. 外面下着雨, 只好呆在家里看看网, 写写代码, 学点编程序的技巧.

http://justjavac.iteye.com/blog/2091899

http://www.sitepoint.com/store/jquery-novice-to-ninja-new-kicks-and-tricks/

http://eng.wealthfront.com/2014/09/from-wall-street-to-silicon-valley.html

http://blog.csdn.net/xudli/article/category/1357583

Sept. 4, 2015

http://blog.csdn.net/sunbaigui/article/details/6335138

10 communication tips from bible

August 23, 2015

Try to improve my communication skills. Here are 10 favorite tips from bible teaching.

1. Listen without interrupting

2. Speak without Accusing

3. Give without Sparing

4. Pray without Ceasing

5. Answer without Arguing

6. Share without pretending

7. Enjoy without Complaint

8. Trust without Wavering

9. Forgive without Punishing

10. Promise without Forgetting

String functions review

August 23, 2015

1. stringDemo.cpp

Including

atoi 5 versions of implementation

https://github.com/jianminchen/stringDemo/blob/master/Program.cs

2. Scramble string:

https://github.com/jianminchen/scramble-string

3. strstr

Boyer-Moore algorithm

https://github.com/jianminchen/stringDemo/blob/master/Program.cs

Read the string function website and get ideas:

http://www-igm.univ-mlv.fr/~lecroq/string/

http://algs4.cs.princeton.edu/53substring/

http://zjalgorithm.blogspot.ca/2014/12/leetcode-in-java-implement-strstr.html

Need a test case to help me figure out Boyer-Moore algorithm again on August 23, 2015.
Here is a short one for me to memorize the idea:
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/StringMatch/boyerMoore.htm

read the article quickly in 20 minutes on August 23, 2015
http://web.cs.ucdavis.edu/~gusfield/cs224f11/bnotes.pdf

Dec. 12, 2015 video watch:
https://www.youtube.com/watch?v=fHNmRkzxHWs
one of examples the presenter gave in his Cpp conference video.
Know that there is a definitely better algorithm than O(n^2), but also, need to know what the ideas are to beat the naive solution. 

Dec. 11, 2015
Need to work on a small test case, therefore, the algorithm can be easily recalled, and ideas of algorithms can be demoed clearly in the example. Go to find my favorite string, substring. (January 5, 2015, read the wiki page, https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm, read 'The bad character rule' and 'The good suffix rule' )

4. longest palindromic string

5. Look up standard string function implementation, quick review and learn:

January 5, 2016
Read the Java code on the following website:
http://algs4.cs.princeton.edu/53substring/BoyerMoore.java.html

Write a C# version, and check in github, and see if it will help to memorize the algorithm. 

Read the webpage: (well written! now Julia knows two rules: bad character rule, the good suffix rule)
https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

http://www.cs.tufts.edu/comp/150GEN/classpages/BoyerMoore.html

Tree algorithms review

August 23, 2015

Here is the list of tree questions worked on:

1. Lowest common ancestor in Binary Tree (January 6, 2016 - Leetcode question: 236 medium)

https://github.com/jianminchen/LowestCommonAncestorInBinaryTree/blob/master/LowestCommonAncestorB.cs

Lowest common ancestor in Binary Search Tree (January 6, 2016 - Leetcode question: 235 easy)
https://github.com/mengli/leetcode/blob/master/LowestCommonAncestorOfaBinarySearchTree.java

https://github.com/jianminchen/Leetcode_C-/blob/master/235LowestCommonAncestorBSearchTree.cs

https://github.com/jianminchen/Leetcode_C-/blob/master/235LowestCommonAncestorBinarySearchTree.cs

2. Leetcode 102: Binary tree level order traversal

a few of implementations:

https://github.com/jianminchen/BTreeLevelOrderTraversal

January 7, 2016 review
https://github.com/jianminchen/BTreeLevelOrderTraversal/blob/master/BTreeLevelOrderTraversal4.cs

3. C# files:

TreeDemo.cpp

  Pre Order Traversal

  In Order Traversal

  Post Order Traversal

  Breadth First Traversal

  Breadth First Traversal Iterative

 Pre Order Traversal Iterative

 Post Order Traversal Iterative*

 In Order Traversal Iterative (A, B two versions)

 Count One Child Node

 Recover Binary Tree

 Invert Binary Tree

 Invert Binary Tree Iterative

 --

Tree Post Order Iterative

Tree In order Iterative

https://github.com/jianminchen/leetcode-tree

4. Tree Max Path Sum

https://github.com/jianminchen/TreeMaxPathSum/blob/master/Program.cs

5. Linked List To Binary Search Tree

https://github.com/jianminchen/LinkedListToBST/blob/master/Program.cs

6. Zigzag order traversal of a binary Tree

http://juliachencoding.blogspot.ca/2015/06/leetcode-zigzag-order-traversal-of.html

7. Maximum Binary Tree Path Sum

How to come out the idea using max value cross root? Cannot recall the idea. 
Read the blog again (8/25/2015):
http://blog.unieagle.net/2012/12/09/leetcode%E9%A2%98%E7%9B%AE%EF%BC%9Abinary-tree-maximum-path-sum/

https://github.com/jianminchen/Leetcode_C-/blob/master/124BinaryTreeMaximumPathSum.cs

The problem can be extended to  a tree, not just a binary tree. The solution is here:
http://juliachencoding.blogspot.ca/2015/07/itint5-tree-maximum-path-sum.html

8. ININT5: tree maximum path sum

http://juliachencoding.blogspot.ca/2015/07/itint5-tree-maximum-path-sum.html

9. Binary Tree Maximum Distance, diameter of binary

http://juliachencoding.blogspot.ca/2015/06/binary-tree-maximum-distance-diameter.html

10. Morris Inorder Traversal

http://juliachencoding.blogspot.ca/2015/06/morris-inorder-traversal-binary-tree.html

11. Convert sorted List to binary search tree (I) (Leetcode question: No. 109)

http://juliachencoding.blogspot.ca/2015/06/leetcode-convert-sorted-list-to.html

12. Convert sorted list to binary search tree (II) (over 3 hours debugging to find a bug) (Leetcode question: No. 109)

http://juliachencoding.blogspot.ca/2015/06/leetcode-sorted-list-to-binary-search.html

August 23, 2015

It is so good to have chance to review post order traversal iterative solution. So, Julia had chance to read more about the problem, understand another solution using space O(log(n)), use a prev variable to keep track of the previously-traversed node. 

Also, she had chance to work out using two stacks solution for post order traversal iterative solution.

Like this, First stack,       root -> left child -> right child, the order of getting into first stack, 

however, second stack, root-> right child -> left child, the order of getting into second stack. 

since left, right child both get into the first stack, then, pop out two of them in reverse order. 

* Read the following blog to help understand post order traversal iterative

http://articles.leetcode.com/2010/10/binary-tree-post-order-traversal.html

C# implementation of post order traversal iterative solution, using prev variable to help:

https://github.com/jianminchen/leetcode-tree/blob/master/TreePostOrderIterative_PrevVarirable.cs

August 24, 2015

13. Convert sorted list to binary search tree (No. 109)
Read the following blogs:
http://articles.leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html

C#, bottom up, time O(n), space O(log n) solution:
https://github.com/jianminchen/Leetcode_C-/blob/master/109ConvertSortedListToBinarySearchTreeB.cs

C#, top down, time O(n^2), space O(long n) solution:

worked on code 2 times, first time, the calculation is kind of messy, then, worked on Leetcode question 108, get the idea to make it more simple; tips like len/2 only shows once, afterwards, use m instead. Just need to improve coding, think to make it more abstract, simple.

https://github.com/jianminchen/Leetcode_C-/blob/master/109ConvertSortedListToBinarySearchTreeC.cs

14. Convert sorted array to binary search tree (No. 108)

https://github.com/jianminchen/Leetcode_C-/blob/master/108ConvertSortedArrayToBinarySearchTree.cs

August 27, 2015
Leetcode Tree questions (29 questions):

94 Binary Tree Inorder Traversal 95 Unique Binary Search Trees II 96 Unique Binary Search Trees 98 Validate Binary Search Tree 99 Recover Binary Search Tree 100 Same Tree 101 Symmetric Tree 102 Binary Tree Level Order Traversal 103 Binary Tree Zigzag Level Order Traversal 104 Maximum Depth of Binary Tree https://github.com/jianminchen/Leetcode_C-/blob/master/104MaximumDepthOfBinaryTree.cs 105 Construct Binary Tree from Preorder and Inorder Traversal 106 Construct Binary Tree from Inorder and Postorder Traversal 107 Binary Tree Level Order Traversal II 108 Convert Sorted Array to Binary Search Tree 109 Convert Sorted List to Binary Search Tree 110 Balanced Binary Tree 111 Minimum Depth of Binary Tree 114 Flatten Binary Tree to Linked List 124 Binary Tree Maximum Path Sum 144 Binary Tree Preorder Traversal 145 Binary Tree Postorder Traversal 156 Binary Tree Upside Down  173 Binary Search Tree Iterator 199 Binary Tree Right Side View 208 Implement Trie (Prefix Tree) 222 Count Complete Tree Nodes 226 Invert Binary Tree 235 Lowest Common Ancestor of a Binary Search Tree 236 Lowest Common Ancestor of a Binary Tree 250 Count Univalue Subtrees
More practice using C#: August 28, 2015
104 Maximum Depth of Binary Tree https://github.com/jianminchen/Leetcode_C-/blob/master/104MaximumDepthOfBinaryTree.c
95 Unique Binary Search Trees II
https://github.com/jianminchen/Leetcode_C-/blob/master/95UniqueBinarySearchTreeII.cs 98 Validate Binary Search Tree Blogs to read:  http://blog.csdn.net/likecool21/article/details/23271621 https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning favorite blog about this problem: http://huntfor.iteye.com/blog/2070278
solutions included in C# practice:  1. recursive, time O(n), using beta-alpha pruning?  2. recursive, use long Max value / min Value instead of int's to avoid the bug  3. use inorder traversal output to help checking BST  4. same as 3, value TreeNode variable  5. sames as 3,  6. same as 3,  7. same as 3, but use iterative solution  8. Great analysis, brute force solution, time complexity O(n^2) vs beta-alpha pruning time O(n)
https://github.com/jianminchen/Leetcode_C-/blob/master/98ValidateBinarySearchTree.cs 99 Recover Binary Search Tree - August 30, 2015 read blogs: http://www.lifeincode.net/programming/leetcode-recover-binary-search-tree-java/ http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html C# implementations: https://github.com/jianminchen/Leetcode_C-/blob/master/99RecoverBinarySearchTree.cs https://github.com/jianminchen/Leetcode_C-/blob/master/99RecoverBinarySearchTreeB.cs work on extracting small functions, and then, understand the algorithm better. https://github.com/jianminchen/Leetcode_C-/blob/master/99RecoveryBinarySearchTree_C.cs 100 same tree blogs to read: http://blog.csdn.net/linhuanmars/article/details/22839819 http://www.cnblogs.com/lautsie/p/3247097.html http://www.cnblogs.com/TenosDoIt/p/3440753.html julia's implementation in C# https://github.com/jianminchen/Leetcode_C-/blob/master/100SameTree.cs
Sept. 5, 2015 Morris order post order traversal blogs to read: http://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html C# implementation: https://github.com/jianminchen/MorrisOrder/blob/master/MorrisPostOrder.cs Morris order in order traversal https://github.com/jianminchen/MorrisInOrderTraverse/blob/master/Program.cs
Sept. 7, 2015 101 Symmetric Tree this one is good to follow use queue http://www.cnblogs.com/TenosDoIt/p/3440729.html LinkedList - as queue - Java http://www.cnblogs.com/springfor/p/3879595.html julia's practice: (Sept. 8, 2015) https://github.com/jianminchen/Leetcode_C-/blob/master/101SymmetricTreeA.cs 105 Construct binary tree from preorder and inorder traversal 106 Construct binary tree from inorder and postorder traversal http://siddontang.gitbooks.io/leetcode-solution/content/tree/construct_binary_tree.html C# practice: https://github.com/jianminchen/Leetcode_C-/blob/master/106ConstructuBTreeFromInorderPostOrderTraversal.cs
second implementation using C#: https://github.com/jianminchen/Leetcode_C-/blob/master/106ConstructBTreeFromInOrderPostOrderTraversal_B.cs
Sept. 13, 2015 208 Implement Trie (prefix tree) blogs: http://pisxw.com/algorithm/Implement-Trie-(Prefix%20Tree).html http://www.jyuan92.com/blog/leetcode-implement-trie-prefix-tree/
August 25, 2015 January 5, 2015 Preorder traversal of ternary tree
https://github.com/jianminchen/TreeAlgorithms/blob/master/ternaryTreeTraversal.cs

  More reading about ternary tree:
https://en.wikipedia.org/wiki/Ternary_search_tree