package leetcode;

/**
 * https://leetcode.com/problems/count-complete-tree-nodes/
 */
public class Problem222 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    private static class Count {
        int count;
        int level;
        boolean done;
    }

    public int countNodes(TreeNode root) {
//        int maxLevel = getNumLevel(root, 0);
//        System.out.println("maxlevel=" + maxLevel);
        Count count = new Count();
        countIncomplete(root, 0, count);
        int maxLevel = count.level + 1;
//        System.out.println("countIncomplete=" + count.count);
        return (int) (Math.pow(2, maxLevel) - 1) - count.count;
    }

    private void countIncomplete(TreeNode node, int level, Count count) {
        if (node == null) {
            if (count.level == 0) {
                count.count++;
                count.level = level;
                return;
            } else if (count.level == level) {
                count.count++;
                return;
            }
//            if (maxLevel > level) {
//                count.count++;
//                return;
//            }
            count.done = true;
            return;
        }
        countIncomplete(node.right, level + 1, count);
        if (count.done) {
            return;
        }
        countIncomplete(node.left, level + 1, count);
        if (count.done) {
            return;
        }
    }

    private int getNumLevel(TreeNode node, int level) {
        if (node == null) {
            return level;
        }
        return getNumLevel(node.left, level + 1);
    }

    public static void main(String[] args) {
        Problem222 prob = new Problem222();

        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.left.left = new TreeNode(4);
        root.left.left.right = new TreeNode(5);
        root.left.right = new TreeNode(6);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(8);
        root.right = new TreeNode(9);
        root.right.left = new TreeNode(10);
        root.right.left.left = new TreeNode(11);
        root.right.right = new TreeNode(12);

        System.out.println(prob.countNodes(root));
    }
}

@@ -274,108 +274,8 @@
  %7D%0A%0A
-    private static class Count %7B%0A        int count;%0A        int level;%0A        boolean done;%0A    %7D%0A%0A
     
@@ -309,26 +309,24 @@
 ode root) %7B%0A
-//
         int 
@@ -325,27 +325,28 @@
     int 
-max
+left
 Level = 
 getNumLe
@@ -337,22 +337,25 @@
 Level = 
-getNum
+countLeft
 Level(ro
@@ -362,26 +362,24 @@
 ot, 0);%0A
-//
         
 System.o
@@ -374,118 +374,48 @@
     
-System.out.println(%22maxlevel=%22 + maxLevel);%0A        Count count = new Count();%0A        countIncomplete
+int rightLevel = countRightLevel
 (root, 0
 , co
@@ -410,23 +410,16 @@
 (root, 0
-, count
 );%0A     
@@ -426,165 +426,177 @@
    i
-nt max
+f (left
 Level =
- count.level + 1;%0A//        System.out.println(%22countIncomplete=%22 + count.count);%0A        return (int) (Math.pow(2, maxLevel) - 1) - count.count
+= rightLevel) %7B%0A            // 2%5Eh - 1%0A            return (1 %3C%3C leftLevel) - 1;%0A        %7D%0A        return 1 + countNodes(root.left) + countNodes(root.right)
 ;%0A  
@@ -616,28 +616,26 @@
 ate 
-void
+int
  count
-Incomplete
+LeftLevel
 (Tre
@@ -659,338 +659,90 @@
 evel
-, Count count) %7B%0A        if (node == null) %7B%0A            if (count.level
+) %7B%0A        int count
  =
-=
  0
-) %7B%0A                count.count++;%0A                count.level = level;%0A                return;%0A            %7D else if (count.level == level) %7B%0A                count.count++;%0A                return;%0A            %7D%0A//            if (maxLevel %3E leve
+;%0A        TreeNode n = node;%0A        while (n != nul
 l) %7B%0A
-// 
     
@@ -749,25 +749,16 @@
         
-   count.
 count++;
@@ -758,20 +758,16 @@
 ount++;%0A
-//  
         
@@ -774,315 +774,51 @@
     
-  return;%0A//            %7D%0A            count.done = true;%0A            return;%0A        %7D%0A        countIncomplete(node.right, level + 1, count);%0A        if (count.done) %7B%0A            return;%0A        %7D%0A        countIncomplete(node.left, level + 1, count);%0A        if (count.done) %7B%0A            return;%0A        %7D
+n = n.left;%0A        %7D%0A        return count;
 %0A   
@@ -837,22 +837,26 @@
 ate int 
-getNum
+countRight
 Level(Tr
@@ -894,210 +894,22 @@
    i
-f (node == null) %7B%0A            return level;%0A        %7D%0A        return getNumLevel(node.left, level + 1);%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem222 prob = new Problem222()
+nt count = 0
 ;%0A
-%0A
     
@@ -925,572 +925,122 @@
 ode 
-root = new TreeNode(1);%0A        root.left = new TreeNode(2);%0A        root.left.left = new TreeNode(3);%0A        root.left.left.left = new TreeNode(4);%0A        root.left.left.right = new TreeNode(5);%0A        root.left.right = new TreeNode(6);%0A        root.left.right.left = new TreeNode(7);%0A        root.left.right.right = new TreeNode(8);%0A        root.right = new TreeNode(9);%0A        root.right.left = new TreeNode(10);%0A        root.right.left.left = new TreeNode(11);%0A        root.right.right = new TreeNode(12);%0A%0A        System.out.println(prob.countNodes(root))
+n = node;%0A        while (n != null) %7B%0A            count++;%0A            n = n.right;%0A        %7D%0A        return count
 ;%0A  

Solve problem 222