二叉树的三种遍历方式

基于递归的遍历

树形DP套路

步骤

  1. 以某个节点X为头结点的子树中,分析答案有哪些可能性,并且这种分析是以X的左子树,X的右子树,和X整棵树的角度来考虑可能性的
  2. 根据第一步分析的可能性,列出所需要的信息,例如在二叉树是否平衡中,左子树和右子树都需要知道各自是否平衡,以及高度这两个信息。
  3. 根据第二步信息汇总,定义自己的信息结构体
  4. 设计递归函数,递归函数是处理以X为头结点的情况相爱的答案,包括设计递归函数的base case,默认直接得到左树和右树所有的信息,以及把可能性左整合,并且返回第三步的信息结构这4个小步骤。