思考重点:分治法
- 二叉树题目几乎全部都要利用分治和递归的思想
简单地解释一下分治法(Divide and Conqueror)
以下解释来自https://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741370.html
- 分治法的设计思想是:将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。
- 分治策略是:对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。
分治法在二叉树题目上的运用
- 根据题目,思考左节点与右节点的关系,并推理出解题所需要返回的值 / 改变的变量
- 分别往左子树和右子树递归
- 确定base case
二叉树题目里面,常出现的分析场景和应对方案
- 询问最大/最小子树
- 定义全局变量去储存最大/最小子树的和
- 通过left + right + root.val 来获取当前子树的值,并和全局变量做比较
- 更新全局变量
2. 通过左右子树的位置来搜索A和B节点的LCA
通过A和B的位置来推算LCA的位置
- 当A或B 等于根,返回根
- 当B是A子树的一部分,而A是左子树的一部分,返回左子树;vice versa
- 当A和B分别在左子树和右子树,返回当前的根
3. 验证当前树是否平衡
从最小子树开始,通过左子树和右子树的关系来推测平衡性
- 返回三个变量:左右子树的值,左右子树的高度,当前根