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.
A:
-------****** 第一遍-----递归---------------
public class Solution { public int countNodes(TreeNode root) { if(root == null) return 0; int l = getDepth(root.left); int r = getDepth(root.right); if(l==r) return 1<<(l+1)+countNodes(root.right); else return 1<<(r+1)+countNodes(root.left); } private int getDepth(TreeNode root){ if(root == null) return 0; return 1+ getDepth(root.left); } }
但上面的会LTE, 原因在于depth计算了多次。
试着把Recursive的 getDepth改成 iterative的 。 依然不行。
----------------------Solution 2 ----------------------
如果从某节点一直向左的高度 = 一直向右的高度, 那么以该节点为root的子树一定是complete binary tree. 而 complete binary tree的节点数,可以用公式算出 2^h - 1. 如果高度不相等, 则递归调用 return countNode(left) + countNode(right) + 1. 复杂度为O(h^2)
public class Solution { public int countNodes(TreeNode root) { if(root==null) return 0; int l = getLeft(root) + 1; int r = getRight(root) + 1; if(l==r) { return (2<<(l-1)) - 1; } else { return countNodes(root.left) + countNodes(root.right) + 1; } } private int getLeft(TreeNode root) { int count = 0; while(root.left!=null) { root = root.left; ++count; } return count; } private int getRight(TreeNode root) { int count = 0; while(root.right!=null) { root = root.right; ++count; } return count; } }
***********上面的是每次查询了最左边和最右边的高度************
********3rd pass, 每次对比左右子树的高度,*********
public class Solution { public int countNodes(TreeNode root) { return helper(root,getHeight(root)); } private int helper(TreeNode root, int height){ if(root == null) return 0; int rightHeight = getHeight(root.right); if(height == rightHeight+1 ){ return (1<<rightHeight) + helper(root.right, rightHeight); }else{ // height == rightHeight + 2 return helper(root.left,height-1) + (1<<rightHeight) ; } } private int getHeight(TreeNode root){ int res = 0; while(root!=null){ res++; root = root.left; } return res; } }
Mistakes:
需要用 移位运算, 如果用Math.pow(a,b)的话,会超时
No comments:
Post a Comment