#leetcode#Count Complete Tree Nodes

</pre>Given a complete binary tree, count the number of nodes.Definition of a complete binary tree from <a target=_blank target="_blank" href="#Types_of_binary_trees" style="color:rgb(0,136,204); text-decoration:none; background:0px 0px">Wikipedia</a>: 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.遇到这题第一反应是BFS，数一遍就知道了， O（n），最基础的解法再怎么减小复杂度呢？比O( n ) 小，也就是 O（logn）了，所以要往二分的方向去想，，对于complete binary tree，最底层的node都是先尽量填满左边的坑，也就是说如果左子树的高度等于右字数的高度，那么左子树是满员的，节点个数为2^leftHeight – 1，加入结果，下一步循环右子树；如果左右子树高度不等，则肯定是右子树高度小于左子树，右字数满员，节点个数是2^rightHeight – 1，加到结果中，下一步循环左子树。不要忘记加 root 的个数 + 1。注意对左右子树高度为0情况的讨论， 2的零次方是1，所以要特殊处理。<pre name="code" class="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) {int res = 0;TreeNode node = root;while(node != null){res++;int leftDepth = getDepth(node.left);int rightDepth = getDepth(node.right);if(leftDepth == rightDepth){res = leftDepth == 0 ? res : res + (1 << leftDepth) – 1;node = node.right;}else{res = rightDepth == 0 ? res : res + (1 << rightDepth) – 1;node = node.left;}}return res;}private int getDepth(TreeNode root){if(root == null)return 0;return getDepth(root.left) + 1;}}

往事是尘封在记忆中的梦，而你是我唯一鲜明的记忆，

相关文章：

你感兴趣的文章：

标签云：