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.