PU Data Structure: Tree

From bottom to top:

• Basic idea:
  • First, check leaves and return a initial value.
  • Second, for no-leaf nodes, we get left-side values and right-side values.
  • merge these two values and return one or several values to the higher level.
• Problems
  • Maximum Depth of Binary Tree
  • Minimum Depth of Binary Tree
  • Balanced Binary Tree
  • Lowest Common Ancestor of a Binary Search Tree [one of solutions]
  • Lowest Common Ancestor of a Binary Tree [one of solutions]
  • Binary Tree Maximum Path Sum
  • Path Sum
  • Count univalue Subtrees (perfect)
  • Diameter of Binary Tree (perfect)
  • Binary Tree Tilt (perfect)
  • Most Frequent Subtree Sum (perfect)
  • Largest BST Subtree (perfect)
  • Find Leaves of Binary Tree (perfect)
  • Lowest Common Ancestor of a Binary Tree (perfect) [with 1/2/3 sign to show whether p/q exist]

From top to bottom:

• Basic idea:
  • First, check current level or the next level and do some operations.
  • recursive call on root->left and root->right.
• Problems:
  • Invert Binary Tree
  • Same Tree
  • Symmetric Tree
  • Populating Next Right Pointers in Each Node
  • Subtree of another tree
  • Validate Binary Search Tree (perfect)
  • Inorder Successor in BST
  • Binary Tree Longest Consecutive Sequence (perfect)
  • Merge Two Binary Tree (perfect)
  • Add One Row to Tree

Inorder traversal:

• Binary Search Tree Iterator
• Find Mode in Binary Search Tree
• Recover Binary Search Tree
• Kth Smallest Element in a BST (perfect)
• Binary Tree Inorder Traversal (perfect)
• Inorder Successor in BST

Preorder traversal:

• Binary Tree Right Side View
• Binary Tree Preorder traversal
• Path Sum II (perfect)
• Sum Root to Leaf Numbers (speical)
• Find Bottom Left Tree Value (perfect)
• Serialize and Deserialize Binary Tree (perfect)

Postorder traversal:

• House Robber III (perfect)
• Binary Tree Postorder Traversal (perfect)

BST attributes:

• Lowest Common Ancestor of a Binary Search Tree
• Convert Sorted Array to Binary Search Tree
• Closest Binary Search Tree Value
• Delete Node in a BST (perfect)

Breadth First Search:

• Binary Tree Level Order Traversal
• Binary Tree Level Order Traversal II
• Binary Tree Right Side View
• Binary Tree Zigzag Level Order Traversal (perfect)
• Add One Row to Tree
• Kill Process (perfect)

Binary Search:

• Closest Binary Search Tree Value

backtracking

• Path Sum III (perfect)

Unique Binary Search Tree: DP
Unique Binary Search Tree II: memoriation
Populating Next Right Pointers in Each Node
Populating Next Right Pointers in Each Node || (perfect)
Construct Binary Tree from Preorder and Inorder Travesal
Construct Binary Tree from Inorder and Postorder Traversal
Flatten Binary Search Tree to Linked List
Binary Tree Upside Down
Sum of Left Leaves
Average of Levels in Binary Tree (perfect)
Construct Binary Tree from String (perfect)
Find Largest Value in Each Tree Row (perfect)