Binary Tree Divide and Conquer

思路

divide and conquer天生就适合在binary tree上，因为左右子树是indepedent的，我们可以indepedently solve the problems of two subtrees然后把结果combine起来。一般来说，divide步骤非常简单，就是recursively call on root.left and root.right。主要的逻辑都发上在conquer(combine)阶段。所以说算法最核心的部分就在于构造return value，我们需要知道子树return 什么value可以被parent tree用到从而解决parent tree的问题。知道这一点，问题就不难解了。

步骤

• 思考recursion需要return 的value
• divide
• conquer

题型

• 证明if true/false的性质：一般是left && right
• 求最大最小值:一般来说是max(left, right) + 1
• count number：一般来说是left + right + 1.
• 求root to leaf node path：这里我们有效path必须是到达leaf node，而只是到达null node应该被视为无效解。
• 还有一种类型是对binary tree进行操作的题目，比如需要move subtree。判断这种问题是否可以应用divide and conquer主要是看这个问题是否可以bottom up解决，如果可以就使用divide and conquer，如果不可以，就使用dfs。
• 凡是需要我们构造树（也就是还没有树）的问题，基本上都是通过divide and conquer解决的，因为我们要先构造子树才能return 给parent root。

  题目

证明true or false

• Leetcode 100. Same Tree
• Leetcode 110. Balanced Binary Tree
• Leetcode 101. Symmetric Tree
• Leetcode 98. Validate Binary Search Tree

求最值

• Leetcode 104. Maximum Depth of Binary Tree
• Leetcode 366. Find Leaves of Binary Tree
• Leetcode 124. Binary Tree Maximum Path Sum
• Leetcode 111. Minimum Depth of Binary Tree
• Leetcode 236. Lowest Common Ancestor of a Binary Tree
• Leetcode 333. Largest BST Subtree
• Leetcode 298. Binary Tree Longest Consecutive Sequence
• Find distance between two nodes in binary tree (Uber店面)这道题其实是LCA的马甲，我们先求出LCA，然后从distance = dis(root, a) + dis(root, b) - 2*dis(root, LCA)

root to leaf问题

• Leetcode 112. Path Sum
• Leetcode 111. Minimum Depth of Binary Tree

构造树类 or 操作类题目(操作类题目其实也可以看做改造／构造树的一种类型）

• Leetcode 108. Convert Sorted Array to Binary Search Tree
• Leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal
• Leetcode 95. Unique Binary Search Trees II
• Leetcode 106. Construct Binary Tree from Inorder and Postorder Traversal
• Leetcode 226. Invert Binary Tree
• Leetcode 156. Binary Tree Upside Down
• Leetcode 109. Convert Sorted List to Binary Search Tree