递归
通俗理解就是定义一个函数然后在函数执行过程中不断地重复调用自己
递归的写法有三个要点:
1.递归的定义(定义好参数,接口)
2.递归的拆解,二叉树中很多问题都是用递归来解决的,比如:
helper(root){
left = helper(root.left);
right = helper(root.right);
}
3.递归的出口,即用if条件句书写各种情况下函数返回值,以及异常情况
http://www.nowamagic.net/librarys/veda/detail/2314
遍历
遍历就是沿着某条搜索路线依次对树中每个结点均做一次且仅做一次访问,在访问的过程中就利用全局变量纪录结果,遍历没返回值, 遍历要么定义全局变量记录结果;要么在主函数中定义,每次作为形参传递给辅助函数
分治
分治是将一个问题分成多个子问题,子问题的解可以合并为该问题的完整解, 合起来这一步是关键,分治需要返回值
PS:
递归只是一种实现方式,分治和递归结合起来比较方便,遍历也可以用非递归实现
分治+遍历的算法可以用分治加ResultType实现
需要多个返回值时定义一个ResultType类型
一般的题都既可以用遍历做也可以用分治来做