二叉树的递归套路

• 最优解的可能性分类

• 具体一点

  public class Info {
      private int yes; // 抢头节点的情况下的以头节点为整树的最大收益
      private int no;// 不抢头节点的情况下的以头节点为整树的最大收益
      public Info(int yes, int no) {
          this.yes = yes;
          this.no = no;
      }
  }
public int rob(TreeNode root) {
    Info info = process(root);
    return Math.max(info.yes, info.no);
}
public Info process(TreeNode node) {
    if (node == null) {
        return new Info(0, 0);
    }
    Info leftInfo = process(node.left);
    Info rightInfo = process(node.right);
    int yes = node.val + leftInfo.no + rightInfo.no;
    int no = Math.max(leftInfo.yes, leftInfo.no) + Math.max(rightInfo.yes, rightInfo.no);
    return new Info(yes, no);
}