Binary Tree & Divide Conquer
分治是把原问题分成(输入)规模更小的但问题相同的子问题。 我们不用再关心子问题如何解决，让它直接调用本函数（递归）即可。 我们要关心的是问题是否能分成子问题，以及子问题的结果返回后如何合并从而解决原问题。 比如convert-sorted-array-to-binary-search-tree，生成二叉搜索树相当于分别生成左右树再合并。 而生成左树的输入范围刚好是中点前段，右树是中点后段，中点本身是root。 这个性质对其中任何再往下分的子问题都满足，因此我们自然可以用分治法来解决。
看到binary tree的题，十有八九是和分治有关。 树的递归定义表明树的左右两棵子树都满足原树的性质，也就是说原问题可以分成两个规模更小的相同子问题。 所以我们可以假设子问题(子树上)已经解决好了，剩下的就是怎么样把子问题的结果合并起来。
当然分治并不局限于binary tree了，排序算法如merge sort和quick sort都是分治思想。分治思想即一个问题可以拆成问题相同只是规模变小了的子问题。
分治在二叉树上的应用本质是个深度优先搜索(或post-order traversal)，和dfs搜索在实现上相比它是没有side effect的，先得到左边的答案，再得到右边的答案，最右合并答案得到最终答案。因此可以用stack帮助实现iterative的post-order解法.
用stack实现traversal有两种方法:
non-backtracking: 简单. 只能用于输出pre和post order结果
backtracking: stack中是(post-order, 等价于分治)或近似是(pre, mid) 一条从root到leaf的path. 过程等价于backtracing dfs. 可广泛用于解二叉树分治题.
Last updated