Given a complete binary tree, count the number of nodes.
Note:
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.
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.
Example:
Input: 1 / \ 2 3 / \ / 4 5 6 Output: 6---------------------
Solution #1, 递归。对比左右子树的 深度,如果相等,则缺口开始在右树,可以把左树的数量全加上。右树类似。
O(lg N * lg N)
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int countNodes(TreeNode root) { if (root == null) return 0; int lh = height(root.left), rh = height(root.right); if (lh == rh) { return 1 + (1 << lh) - 1 + countNodes(root.right); }else { return 1 + (1 << rh) - 1 + countNodes(root.left); } } private int height(TreeNode root) { int h = 0; while (root != null) { h++; root = root.left; } return h; } }
Solution #2, 迭代写法
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int countNodes(TreeNode root) { if (root == null) return 0; int h = height(root) - 1; int count = 0; while (root != null) { if (height(root.right) == h - 1) { count += 1 + (1 << (h - 1)) - 1; root = root.left; }else { count += 1 + (1 << h) - 1; root = root.right; } h--; } return count; } private int height(TreeNode root) { int h = 0; while (root != null) { h++; root = root.left; } return h; } }
No comments:
Post a Comment