package lcp26;

/**
 * 我们标记每个点的状态：
 * 0：表示该点及孩子们都不放导航装置；
 * 1：表示左右孩子都没有导航装置时，必须选一个孩子支路放一个导航装置，另一个暂时不放，以1状态标记交上面节点去处理；
 * 2：表示左右孩子支路都有导航装置，该节点的父节点支路可以放也可以不放导航装置。
 */
public class Solution {

  private int result;

  public int navigation(TreeNode root) {
    if (root == null) {
      return 0;
    }
    //根节点单独处理
    int left = dfs(root.left);
    int right = dfs(root.right);
    //下面这行代码是多种状态综合处理的表现形式，具体如下：
    //左右孩子状态集(左右交换就不写了)：
    //[0,0]：左右都没放导航(包含子树为空的情况)，那么要必须放一个导航，即res+1，而且总共放一个导航；
    //[0,1]：一个孩子没放导航，再和根节点放一起，视为最近的三叉点的一条支路。由于另一个孩子状态为1，表示该三叉点有两条支路未放导航，所以还要再增加一个导航，那么res+1；
    //[0,2]：一个孩子没放导航，再和根节点放一起，视为最近的三叉点的一条支路。另一个孩子状态为2，表示该三叉点有两条支路已放导航，所以不用再增加导航，返回res即可；
    //[1,1]：其中一个孩子和根节点放一起，视为一条支路，那么就表示该合并后的支路上有导航（只要有就可以了），所以该三叉点的两条支路有导航，返回res即可；
    //[1,2]：前面同上，该三叉点的三条支路都有导航，返回res即可；
    //[2,2]：直接同上。
    //综合上面分类情况，左右返回的状态值相加left+right>=2时，返回res即可，其他情况都要再加一个导航。
    if (left + right >= 2) {
      return result;
    }
    return result + 1;
  }

  public int dfs(TreeNode root) {
    //为空时，表示没放导航
    if (root == null) {
      return 0;
    }
    int left = dfs(root.left);
    int right = dfs(root.right);
    //由于上面根节点单独处理，所以这里只要左右不为空，即为三叉点
    if (root.left != null && root.right != null) {
      //左右子树都没放导航，那么必须选一条支路放一个导航，另一条支路暂时不放，返回状态1；
      if (left == 0 && right == 0) {
        result++;
        return 1;
      }
      //一条支路有导航，另一条支路没有导航，继续暂时不放，返回状态1，要不要加交给上面节点来判断处理；
      //这里多说一句，由于该三叉节点一条有导航另一条没导航，那么对于之前已经遍历的下面的三叉点来说，相当于它的父节点支路有导航了，所以当时处理它时，是否有一条支路未放导航就无所谓了；
      if (left == 0 || right == 0) {
        return 1;
      }
      //左右孩子支路都有导航，那么就返回状态2
      return 2;
    }
    if (root.left == null) {//左孩子为空，该节点状态等于右孩子，或者说把最近的三叉点状态往上传递
      return right;
    }
    return left;
  }

}