Binary Tree DFS Traversal

思路

我们一般在三个情形下会用到top down dfs。第一种是题目要求我们做preorder/inorder/postorder的traversal，或是写出他们的iterator，那么我们只能用dfs traversal的方法自上而下。第二种是题目找所有的具体可行方案，那么这种情况下，我们就需要用到dfs backtracking的思想。最后如果题目只能通过自上而下的方式而非自下而上，那么我们需要使用dfs。

一般来说，traversal里面preorder是最好用的，因为顺序是根，左，右。所以我们可以直接处理当前root的逻辑。

题型

• iterator：如果要写iterator,一般我们要写iterative的栈操作。
• 返回所有path: dfs backtracking
• 根据depth划分层级：一般这种问题需要我们记录以depth为key的层级信息。

  题目

traversal类

inorder

• Leetcode 173. Binary Search Tree Iterator (难点是iterative)
• Leetcode 99. Recover Binary Search Tree
• Leetcode 94. Binary Tree Inorder Traversal

preorder

• Leetcode 144. Binary Tree Preorder Traversal (难点是iterative)
• Leetcode 114. Flatten Binary Tree to Linked List (Facebook店面考了iterative)
• Leetcode 404. Sum of Left Leaves
• Leetcode 314. Binary Tree Vertical Order Traversal (Facebook店面，这道题更直观的解法是BFS因为可以保证从上到下，如果用DFS可能会出问题，所以我们还得针对每一个offset list的depth进行排序，时间复杂度更高)

postorder

• Leetcode 145. Binary Tree Postorder Traversal (难点是iterative)

返回所有具体path

• Leetcode 257. Binary Tree Paths
• Leetcode 113. Path Sum II

根据depth划分层级

• Leetcode 199. Binary Tree Right Side View