222. Count Complete Tree Nodes

本题不算很难，但是没做出来并不冤，算是Medium题里面比较巧妙的
算法是二分搜索，但是并不像传统的二分搜索可以精确的取中点。

• 我们把height定义为一直往左走的深度
  
• 对节点2来说，height 为3
  
• 对节点3来说，height 也是3
  

• 当left和right高度相同

  • 证明左子树必然是FULL的，右子树则不一定
    
  • 左边连带Root即1，一共有个点
  • 然后recursive，把4作为root，继续计算
    • 左子树6: height为2
      
    • 右子树7：height为1
      
    • left right不同：
      • 证明右子树必然是FULL，左子树必然不是
        
      • 右边连带Root：4 一共个点
      • 然后recursive计算以6为Root的子树
        ```java /**
        • Definition for a binary tree node.
        • public class TreeNode {
        • int val;
        • TreeNode left;
        • TreeNode right;
        • TreeNode() {}
        • TreeNode(int val) { this.val = val; }
        • TreeNode(int val, TreeNode left, TreeNode right) {
        • this.val = val;
        • this.left = left;
        • this.right = right;
        • }
        • } */ class Solution { public int countNodes(TreeNode root) { if (root == null) { return 0; } int leftHeight = getLeftHeight(root.left); int rightHeight = getLeftHeight(root.right); if (leftHeight == rightHeight) { // left is FULL, right probably is not FULL return (1 << leftHeight) + countNodes(root.right); } else { // right is FULL, left is NOT full return (1 << rightHeight) + countNodes(root.left); } }

  private int getLeftHeight(TreeNode node) { int height = 0; while (node != null) {

  node = node.left;
  ++height;

  } return height; } } ```