Tree

Tree

Overview

Tree类型问题还是比较有普遍性的，没有太多需要奇技淫巧的地方，一般可以这么思考

1. 考虑DFS还是BFS
2. 如果是DFS的话是从上往下还是下往上
3. 优化的方向主要包括：简单的剪枝(Trim)、加入memo、结合dp

不过也有一些问题披着Tree的外皮，考你其他东西，这里就不点名了hhh

Tree Construction

• Serialize and Deserialize Binary Tree
  • 方法有 DFS BFS 用括号啥的，前两种够用了
  • DFS的话考虑到deserialize时候方便还是preorder比较好
• Serialize and Deserialize N-ary Tree
  • 用DFS的话可以考虑把每个node children的个数也纳入其中，或者在结尾额外加一个分隔符
• Serialize and Deserialize BST
• Construct Binary Tree from Preorder and Inorder Traversal
• Construct Binary Tree from Inorder and Postorder Traversal
  • 包含inorder还是很简单的
  • 用一个hashmap存 Val, Index 就可以O(n)
• Construct Binary Tree from Preorder and Postorder Traversal
  • 如果不用复杂的边界条件的话，我们可以继续用preorder的array作为基准，但是我们在postorder中寻找的点并不是当前preorder的值，而是preorder array中的左右子树的起止点。
• Construct Binary Search Tree from Preorder Traversal
  • 最直接的当然是强行加一个inorder然后转换成上面那题，O(nlogn)
  • 也可以利用边界直接构建 O(n)，此时要注意的是在寻求min max边界时需要一个试错的过程，所以不能立马让preorder的index++
• Unique Binary Search Trees
• Unique Binary Search Trees II
• Flatten Binary Tree to Linked List
  • 思路需要再看看，利用leftTail和rightTail很巧妙
• Convert Binary Search Tree to Sorted Doubly Linked List
• Minimum Cost Tree From Leaf Values *
  • 虽然是个dp问题，还是放在construction里面了

Traversal

虽然Tree的问题除了上面的构成大多都是遍历问题，但是下面的遍历问题主要指通过遍历得到一组值。当然最基本的DFS inorder, preorder, postorder 的recursion 和 iteration方法、BSF的iteration还是要烂熟于心的hh

• Binary Search Tree Iterator
• Binary Tree Right Side View
• Vertical Order Traversal of a Binary Tree
• Binary Tree Vertical Order Traversal
• Validate Binary Search Tree
• Binary Tree Zigzag Level Order Traversal
• Recover Binary Search Tree
  • 正常算法就好。。
  • Morris kankan
• Boundary of Binary Tree
• Find Leaves of Binary Tree
• Populating Next Right Pointers in Each Node II
• Binary Tree Paths
• Maximum Difference Between Node and Ancestor
• Count Complete Tree Nodes
• Maximum Width of Binary Tree
• Largest BST Subtree
• Flip Equivalent Binary Trees
• Inorder Successor in BST
• Merge Two Binary Trees
  • 用原来的TreeNode会比新建方便很多
• Inorder Successor in BST II
• Count Univalue Subtrees

Path Sum

• Binary Tree Maximum Path Sum
• Range Sum of BST
• Path Sum
• Path Sum II
• Path Sum III
  • 用 prefix sum 有两个细节：当前sum等于target时要考虑，所以hashmap要加入0 key；先更新hashmap还是先找complement
• Distribute Coins in Binary Tree
  • 难点在于怎么抽象分硬币的过程
• Sum Root to Leaf Numbers
• House Robber III

Depth

• Diameter of Binary Tree
• Maximum Depth of Binary Tree
• Lowest Common Ancestor of Deepest Leaves
• Smallest Subtree with all the Deepest Nodes

Find Node(s)

• Lowest Common Ancestor of a Binary Search Tree
• All Nodes Distance K in Binary Tree
• Delete Nodes And Return Forest

Others

• Find All The Lonely Nodes - Find specific nodes
• Merge Two Binary Trees - Combine two binary trees
• Search in a Binary Search Tree - Find specific nodes
• N-ary Tree Preorder Traversal - Traversal
• Increasing Order Search Tree - BST + linked list
• Maximum Depth of N-ary Tree - Depth
• Univalued Binary Tree - Traversal
• Sum of Root To Leaf Binary Numbers - Traversal and tricks about binary
• Leaf-Similar Trees
• Invert Binary Tree - Exchange nodes
• Trim a Binary Search Tree - Swap nodes
• Convert Sorted Array to Binary Search Tree - Construct BST
• Convert BST to Greater Tree - BST
• Construct String from Binary Tree - Construct
• Minimum Absolute Difference in BST - How to track previous val if not using global variables
• Same Tree - Traveseral
• Cousins in Binary Tree - Branch prune
• Binary Tree Paths - String & StringBuilder
• Smallest Common Region - LCA