Sunday, August 23, 2015

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)

2. Leetcode 102: Binary tree level order traversal
a few of implementations:

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


4. Tree Max Path Sum


5. Linked List To Binary Search Tree


6. Zigzag order traversal of a binary Tree


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


9. Binary Tree Maximum Distance, diameter of binary


10. Morris Inorder Traversal


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


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



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

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
95
96
98
99
100
101
102
103
104
105
106
107
108
109
110
111
114
124
144
145
156
173
199
208
222
226
235
236
250


More practice using C#:
August 28, 2015
104
95
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

LinkedList - as queue - Java

105 Construct binary tree from preorder and inorder traversal

106 Construct binary tree from inorder and postorder traversal


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




No comments:

Post a Comment