content: 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;
    }
  
  }