LeetCode/222_Count_Complete_Tree_Nodes at master · KnowledgeCenterYoutube/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// LeetCode 222: Count Complete Tree Nodes
// Detailed Explanation available here: https://youtu.be/i_r2uKbwHCU

// C++:
int countNodes(TreeNode* root) {
    if(!root) return 0;
    TreeNode *left = root, *right = root;
    int h_l = 0, h_r = 0;
    while(left){
        h_l++;
        left = left->left;
    }
    while(right){
        h_r++;
        right = right->right;
    }
    if(h_l == h_r) return (1<<h_l) - 1;

    return 1 + countNodes(root->left) + countNodes(root->right);
}

// Java:
public int countNodes(TreeNode root) {
        if(root == null) return 0;
        TreeNode left = root, right = root;
        int h_l = 0, h_r = 0;
        while(left != null){
            h_l++;
            left = left.left;
        }
        while(right != null){
            h_r++;
            right = right.right;
        }
        if(h_l == h_r) return (1<<h_l) - 1;

        return 1 + countNodes(root.left) + countNodes(root.right);
}

# Python3:
def countNodes(self, root: TreeNode) -> int:
    if root == None: return 0
    left, right = root, root
    h_l, h_r = 0, 0
    while left != None:
        h_l += 1
        left = left.left

    while right != None:
        h_r += 1
        right = right.right

    if h_l == h_r: return (1<<h_l) - 1

    return 1 + self.countNodes(root.left) + self.countNodes(root.right)

** Please share and Subscribe the Channel **