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.

- 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

- 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

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

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.