Binary Tree - Algorithm

Binary tree
- post order traverse
- what state need to store and pass
- inorder and preorder/postorder uniquely identify a binary tree
- preorder uniquely identify a bst

Height
- The height of a node is the number of edges from the node to the deepest leaf

how to make code clean
return isBST2(root.left, min, root.data) && isBST2(root.right, root.data, max);


LeetCode 366 - Find Leaves of Binary Tree
- Use HashMap
Tree Amplitude


LeetCode 314 Binary Tree Vertical Order Traversal
- Level Order traversal Map> map
- DFS

LeetCode 404 - Sum of Left Leaves
- BFS

X. Post order traverse

LeetCode 110 - Balanced Binary Tree
- Stack

LeetCode - 563 Binary Tree Tilt
The tilt of a tree node is defined as the absolute difference between the sum of all left subtree node values and the sum of all right subtree node values.

LeetCode 513 - Find Bottom Left Tree Value
find the leftmost value in the last row of the tree.
- Recursion
- Level Order traversal
- Level Order traversal  but right then left

Diagonal Sum of a Binary Tree
- Queue queue, Map map: vd->sum

LintCode - 596 Minimum Subtree


X. Return multiple info
Leetcode 124 - 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.
return Math.max(left, right) + node.val;
http://ying.ninja/?p=964
private class maxPathResult {
    int maxSinglePath;
    int maxPath;
}

LeetCode 298 - Binary Tree Longest Consecutive Sequence
The longest consecutive path need to be from parent to child (cannot be the reverse).

LeetCode 549 - Binary Tree Longest Consecutive Sequence II
this path can be either increasing or decreasing, the path can be in the child-Parent-child order
https://discuss.leetcode.com/topic/85745/java-solution-binary-tree-post-order-traversal
https://xuezhashuati.blogspot.com/2017/04/lintcode-619-binary-tree-longest.html

LeetCode 543 - Diameter of a Binary Tree
- post order traverse
- return diameter and height
int finalDiameter = getMax(leftDiameter, rightDiameter, rootDiameter);

X. Serialize and deserialize tree
LeetCode 536 - Construct Binary Tree from String - 4(2(3)(1))(6(5))
You always start to construct the left child node of the parent first if it exists.
- current, leftChild, rightChild
- Stack https://discuss.leetcode.com/topic/82605/java-stack-solution/
  - stack peek is parent

LeetCode 606 - Construct String from Binary Tree 1(2(4))(3)
- Stack

LeetCode 449 - Serialize and Deserialize BST
- Don't use null node

LeetCode 331 - Verify Preorder Serialization of a Binary Tree
- Use stack that emulates creating the tree
- in/out degree

Trie Serialization
Serialize and Deserialize an N-ary Tree

Google – Find Duplicated Subtrees
- Use string to represent the tree
TODO Check if a Binary Tree contains duplicate subtrees of size 2 or more

LeetCode 572 - Subtree of Another Tree

LeetCode 623 - Add One Row to Tree
- BFS
- DFS

LeetCode 96 - Unique Binary Search Trees I
how many structurally unique BST's (binary search trees) that store values 1...n?
f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ... + f(n-2)*f(1) + f(n-1)*f(0)
- Catalan Number

TODO
LeetCode 95 - Unique Binary Search Trees II
generate all structurally unique BST's (binary search trees) that store values 1...n.

Labels

Java (159) Lucene-Solr (112) Interview (61) All (58) J2SE (53) Algorithm (45) Soft Skills (38) Eclipse (33) Code Example (31) Linux (25) JavaScript (23) Spring (22) Windows (22) Web Development (20) Tools (19) Nutch2 (18) Bugs (17) Debug (16) Defects (14) Text Mining (14) J2EE (13) Network (13) Troubleshooting (13) PowerShell (11) Chrome (9) Design (9) How to (9) Learning code (9) Performance (9) Problem Solving (9) UIMA (9) html (9) Http Client (8) Maven (8) Security (8) bat (8) blogger (8) Big Data (7) Continuous Integration (7) Google (7) Guava (7) JSON (7) Shell (7) ANT (6) Coding Skills (6) Database (6) Lesson Learned (6) Programmer Skills (6) Scala (6) Tips (6) css (6) Algorithm Series (5) Cache (5) Dynamic Languages (5) IDE (5) System Design (5) adsense (5) xml (5) AIX (4) Code Quality (4) GAE (4) Git (4) Good Programming Practices (4) Jackson (4) Memory Usage (4) Miscs (4) OpenNLP (4) Project Managment (4) Spark (4) Testing (4) ads (4) regular-expression (4) Android (3) Apache Spark (3) Become a Better You (3) Concurrency (3) Eclipse RCP (3) English (3) Happy Hacking (3) IBM (3) J2SE Knowledge Series (3) JAX-RS (3) Jetty (3) Restful Web Service (3) Script (3) regex (3) seo (3) .Net (2) Android Studio (2) Apache (2) Apache Procrun (2) Architecture (2) Batch (2) Bit Operation (2) Build (2) Building Scalable Web Sites (2) C# (2) C/C++ (2) CSV (2) Career (2) Cassandra (2) Distributed (2) Fiddler (2) Firefox (2) Google Drive (2) Gson (2) How to Interview (2) Html Parser (2) Http (2) Image Tools (2) JQuery (2) Jersey (2) LDAP (2) Life (2) Logging (2) Python (2) Software Issues (2) Storage (2) Text Search (2) xml parser (2) AOP (1) Application Design (1) AspectJ (1) Chrome DevTools (1) Cloud (1) Codility (1) Data Mining (1) Data Structure (1) ExceptionUtils (1) Exif (1) Feature Request (1) FindBugs (1) Greasemonkey (1) HTML5 (1) Httpd (1) I18N (1) IBM Java Thread Dump Analyzer (1) JDK Source Code (1) JDK8 (1) JMX (1) Lazy Developer (1) Mac (1) Machine Learning (1) Mobile (1) My Plan for 2010 (1) Netbeans (1) Notes (1) Operating System (1) Perl (1) Problems (1) Product Architecture (1) Programming Life (1) Quality (1) Redhat (1) Redis (1) Review (1) RxJava (1) Solutions logs (1) Team Management (1) Thread Dump Analyzer (1) Visualization (1) boilerpipe (1) htm (1) ongoing (1) procrun (1) rss (1)

Popular Posts