Skip to content

Latest commit

 

History

History
203 lines (170 loc) · 12.6 KB

tree.md

File metadata and controls

203 lines (170 loc) · 12.6 KB

Tree

144.Binary-Tree-Preorder-Traversal (M+)
145.Binary-Tree-Postorder-Traversal (H-)
270.Closest-Binary-Search-Tree-Value (M+)
095.Unique-Binary-Search-Trees-II (H)
094.Binary Tree Inorder Traversal (H-)
110.Balanced-Binary-Tree (M+)
124.Binary-Tree-Maximum-Path-Sum (M+)
222.Count-Complete-Tree-Nodes (M+)
099.Recover-Binary-Search-Tree (H)
114.Flatten-Binary-Tree-to-Linked-List (M+)
098.Validate-Binary-Search-Tree (M)
117.Populating Next Right Pointers in Each Node II (H)
156.Binary-Tree-Upside-Down (H)
285.Inorder-Successor-in-BST (M)
298.Binary-Tree-Longest-Consecutive Sequence (M+)
450.Delete-Node-in-a-BST (H)
437.Path-Sum-III (H-)
333.Largest-BST-Subtree (H)
543.Diameter-of-Binary-Tree (M+)
572.Subtree-of-Another-Tree (M)
549.Binary-Tree-Longest-Consecutive-Sequence-II (M)
173.Binary-Search-Tree-Iterator (M)
545.Boundary-of-Binary-Tree (H-)
272.Closest-Binary-Search-Tree-Value-II (M+)
310.Minimum-Height-Trees (H-)
226.Invert-Binary-Tree (M)
655.Print-Binary-Tree (M+)
897.Increasing-Order-Search-Tree (M+)
501.Find-Mode-in-Binary-Search-Tree (M+)
558.Quad-Tree-Intersection (M+)
662.Maximum-Width-of-Binary-Tree (H-)
687.Longest-Univalue-Path (M+)
742.Closest-Leaf-in-a-Binary-Tree (H)
834.Sum-of-Distances-in-Tree (H)
863.All-Nodes-Distance-K-in-Binary-Tree (H-)
958.Check-Completeness-of-a-Binary-Tree (M+)
1339. Maximum-Product-of-Splitted-Binary-Tree (TBD)
1104.Path-In-Zigzag-Labelled-Binary-Tree (M+)
1660.Correct-a-Binary-Tree (M+)
1666.Change-the-Root-of-a-Binary-Tree (H-)
1932.Merge-BSTs-to-Create-Single-BST (H)
2003.Smallest-Missing-Genetic-Value-in-Each-Subtree (H)

Serialization & Hashing

297.Serialize-and-Deserialize-Binary-Tree （H-）
652.Find-Duplicate-Subtrees (H)
1948.Delete-Duplicate-Folders-in-System (H)

Traversal

  • Classic tree level order traversal with O(n) space
bfsQueue = deque()
bfsQueue.append( root )
while bfsQueue:
  head = bfsQueue.popleft()
  // do stuff
  if head.left is not None:
    bfsQueue.append(head.left)
  if head.right is not None:
    bfsQueue.append(head.right)
  • Special tree level order traversal with O(1) space: example problem (populate next right pointers in each node II)

Get inorder traversal predecessor/successor

    def getPredecessor(root: TreeNode, target: TreeNode) -> TreeNode:
      if target.left:
        currNode = target.left
        while currNode.right:
          currNode = currNode.right
        return currNode
      else:
        predecessor = None
        currNode = root
        while currNode != target:
          if currNode.val >= target.val:
            currNode = currNode.left
          else:
            predecessor = currNode
            currNode = currNode.right
        return predecessor

    def getSuccessor(root: TreeNode, target: TreeNode) -> TreeNode:
      if target.right:
        currNode = target.right
        while currNode.left != null:
          currNode = currNode.left
        return currNode
      else:
        successor = None
        currNode = root
        while currNode != target:
          if currNode.val >= target.val:
            successor = currNode
            currNode = currNode.left
          else:
            currNode = currNode.right
        return successor

Tree & Sequence

105.Construct-Binary-Tree-from-Preorder-and-Inorder-Traversal (H-)
106.Construct-Binary-Tree-from-Inorder-and-Postorder-Traversal (M+)
331.Verify-Preorder-Serialization-of-a-Binary-Tree (H)
449.Serialize-and-Deserialize-BST (H)
971.Flip-Binary-Tree-To-Match-Preorder-Traversal (M+)
1028.Recover-a-Tree-From-Preorder-Traversal (H-)
1569.Number-of-Ways-to-Reorder-Array-to-Get-Same-BST (H)
1597.Build-Binary-Expression-Tree-From-Infix-Expression (H)
1902.Depth-of-BST-Given-Insertion-Order (H-)

LCA

Problem and BF

  • Generic problem: Find lowest common ancestor for M nodes in a N-ary tree
  • BF solution: Find root to node paths for M nodes as M list. Then compare M list together to find the first diff element.
    • T.C. : build path O(M * SIZE(tree)) and find common LCA O(SIZE(tree) * M)
    • S.C. : O(M * SIZE(tree))

Improved solution thoughts

# pseudo code:
# Find the first node whose children + itself covers the entire target during the tree DFS process
(resultContained, resultNode) = recursion(root, [target1, ..., targetN])
  resultContained = 0
  resultNode = None
  for child in root.children:
    childContained, childResult = recursion(child, [target1, ..., targetN])
    if childContained == len(targetSet):
      return (childContained, childResult)
    else:
      resultContained += childContained
  
  if root.value in targetSet:
    resultContained += 1
    if resultContained == len(targetSet):
      resultNode = root
  return (resultContained, resultNode)

Example problems

236.Lowest-Common-Ancestor-of-a-Binary-Tree (H)
1676.Lowest-Common-Ancestor-of-a-Binary-Tree-IV (M+)
1740.Find-Distance-in-a-Binary-Tree (H)

N-ary Tree

428.Serialize-and-Deserialize-N-ary-Tree (H)
431.Encode-N-ary-Tree-to-Binary-Tree (H-)
1516.Move-Sub-Tree-of-N-Ary-Tree (H-)

似树非树

823, 1902,

Segment Tree

Basics

307.Range-Sum-Query-Mutable (H-)
1526.Minimum-Number-of-Increments-on-Subarrays-to-Form-a-Target-Array (H-)
1649.Create-Sorted-Array-through-Instructions (H-)
1157.Online-Majority-Element-In-Subarray (H)

Lazy Tag

370.Range-Addition (H)
218.The-Skyline-Problem (H+)
699.Falling-Squares (H)

Others

715.Range-Module (H)

[Binary Index Tree]

307.Range-Sum-Query-Mutable (M)
1649.Create-Sorted-Array-through-Instructions (H)