Given a complete binary tree, count the number of nodes.
Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
Understand the problem:In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
First of all, what is a complete binary tree?
A complete binary tree is a binary tree where each level except for the last level is full.
A naive solution:
A naive solution is just to traverse the tree and count the number of nodes. The time complexity is O(n). It gets the Time Limit Exceeded.
A Better Solution:
A better idea is to get the height of the left-most part, and height of the right-most part. If the left height and right height are the same, means the tree is full. Then the number of nodes is 2^h - 1. If not, we recursively count the number of nodes for the left sub-tree and right sub-tree.
Code (Java):
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public int countNodes(TreeNode root) { if (root == null) { return 0; } int leftHeight = findLeftHeight(root); int rightHeight = findRightHeight(root); if (leftHeight == rightHeight) { return (2 << (leftHeight - 1)) - 1; } return countNodes(root.left) + countNodes(root.right) + 1; } private int findLeftHeight(TreeNode root) { if (root == null) { return 0; } int height = 1; while (root.left != null) { height++; root = root.left; } return height; } private int findRightHeight(TreeNode root) { if (root == null) { return 0; } int height = 1; while (root.right != null) { height++; root = root.right; } return height; } }
The time complexity is O(h^2), because calculating the height of a binary tree takes O(h) time, and it recursively traverse the tree by O(h) time.
In more detail, in worst case, we need to calculate the height of the tree in 1 + 2 + 3 + 4 + ... + h = O(h^2) time. It is actually 2 * O(h^2) because we need to calculate the left and right height.
No comments:
Post a Comment