In this Leetcode Count Complete Tree Nodes problem solution we have Given the root of a complete binary tree, return the number of the nodes in the tree.
Problem solution in Python.
class Solution: def countNodes(self, root: TreeNode) -> int: if not root: return 0 frontier = [root] level = 0 last = None while frontier: new = [] level += 1 for node in frontier: if node.left == None or node.right == None: # last is the last level with full nodes last = level new.append(node.left) new.append(node.right) if last == None: frontier = new else: temp = 0 for i in range(last): temp += 2**i return len([elt for elt in new if elt != None]) + temp
Problem solution in Java.
int count = 0; public int countNodes(TreeNode root) { helper(root); return count; } private void helper(TreeNode node){ if (node == null) return; count++; helper(node.left); helper(node.right); }
Problem solution in C++.
class Solution { public: int countNodes(TreeNode* root) { int res = 0; int depth = 0; int tmp = 0; int cnt = 0; bool flag = true; bool virgin = true; countNodesDFS(root, depth, tmp, cnt, flag, virgin); int plus = 1; for(int i = 0; i < depth; i++){ res += plus; plus *= 2; } res = res - (plus / 2) + (cnt / 2); return res; } void countNodesDFS(TreeNode* cur, int& depth, int &tmp, int &cnt, bool &flag, bool &virgin){ if(flag == false) return; if(cur == NULL){ if(virgin == true){ depth = tmp; virgin = false; } if(tmp == depth) cnt++; else flag = false; return; } tmp += 1; countNodesDFS(cur->left, depth, tmp, cnt, flag, virgin); countNodesDFS(cur->right, depth, tmp, cnt, flag, virgin); tmp -= 1; } };
Problem solution in C.
void count_nodes(struct TreeNode* root, int* size){ if(root==NULL){ *size=0; return; } int l_subtree_size, r_subtree_size; count_nodes(root->left, &l_subtree_size); count_nodes(root->right, &r_subtree_size); *size=l_subtree_size+r_subtree_size+1; } int countNodes(struct TreeNode* root){ int size=0; count_nodes(root, &size); return size; }
0 Comments