222. Count Complete Tree Nodes
Last updated
Last updated
// 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;
}
}/**
* Time complexity : O(N)
* Space complexity : O(d)=O(logN) to keep the recursion stack,
* where d is a tree depth.
*/
class Solution {
public int countNodes(TreeNode root) {
if(root == null) return 0;
return 1 + countNodes(root.left) + countNodes(root.right);
}
}/**
* Time complexity :
* Space complexity :
*/
class Solution {
public int countNodes(TreeNode root) {
if(root == null) return 0;
int left = getLeftHeight(root) + 1;
int right = getRightHeight(root) + 1;
if(left == right) {
return (2 << (left-1))-1;
}
return 1 + countNodes(root.left) + countNodes(root.right);
}
private int getLeftHeight(TreeNode node) {
if(node == null) return 0;
int height = 0;
while(node.left != null) {
height++;
node = node.left;
}
return height;
}
private int getRightHeight(TreeNode node) {
if(node == null) return 0;
int height = 0;
while(node.right != null) {
height++;
node = node.right;
}
return height;
}
}