My code:
/**
* 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 left = 1 + getLeftHeight(root);
int right = 1 + getRightHeight(root);
if (left == right)
return (1 << left) - 1;
else
return 1 + countNodes(root.left) + countNodes(root.right);
}
private int getLeftHeight(TreeNode root) {
if (root == null)
return 0;
int height = 0;
while (root.left != null) {
height++;
root = root.left;
}
return height;
}
private int getRightHeight(TreeNode root) {
if (root == null)
return 0;
int height = 0;
while (root.right != null) {
height++;
root = root.right;
}
return height;
}
public static void main(String[] args) {
Solution test = new Solution();
TreeNode n1 = new TreeNode(1);
System.out.println(test.countNodes(n1));
}
}
My test result:
这道题目最简单的做法，就是直接随便遍历。但肯定是不对的，太慢了。
我也在想办法，利用完整树的特性。
但是最后没做出来。
具体做法看下这个博客吧。写的很清楚。
http://www.programcreek.com/2014/06/leetcode-count-complete-tree-nodes-java/
programcreek 好网站
**
总结： 之前有道题目，kth Smallest number 也是采用了把树劈成两半，左右各自统计结点个数。
而这道题目，同样是左右各自遍历。虽然具体细节不同。
但是可以看出，这也算是树的遍历方式的一种。
Tree 免费的medium和easy差不多都做完了，还差两道easy。
感觉树的遍历方式有如下几种。
pre-order top-down
in-order sort-order for BST
post-order bottom-up
然后递归形式我可以很轻松地写出来。但是非递归形式不会写。
所以这三种遍历的非递归，要在这周末前学会写！！！！
然后，level-order
left to right
right to left
zigzag (use two stacks)
然后，
这道题目的遍历方式，分别遍历左子树与右子树，统计信息。
然后继续遍历左子树的左子树与右子树。。。。
以此循环。
同时，设置一些全局的私有变量，有时候会方便写代码。
**
Anyway, Good luck, Richardo!
My code:
/**
* 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;
return helper(root);
}
private int helper(TreeNode root) {
if (root == null)
return 0;
int left = getLeftDepth(root);
int right = getRightDepth(root);
if (left == right)
return (int) (2 << (left - 1)) - 1;
else
return 1 + helper(root.left) + helper(root.right);
}
private int getLeftDepth(TreeNode root) {
int counter = 0;
while (root != null) {
counter++;
root = root.left;
}
return counter;
}
private int getRightDepth(TreeNode root) {
int counter = 0;
while (root != null) {
counter++;
root = root.right;
}
return counter;
}
}
这道题目第二次做还是没做出来。
就是用二分法做。
其中， 用左移位求 2 ^ n 速度更快。 如果用 Math.pow(2, n); 会超时。
参考网页：
http://www.programcreek.com/2014/06/leetcode-count-complete-tree-nodes-java/
另外，衍生出来一个问题，如果判断一棵树是不是complete
我写了一段代码如下：
My code:
public boolean isFullBT(TreeNode root) {
if (root == null)
return false;
Queue<TreeNode> q = new LinkedList<TreeNode>();
q.offer(root);
boolean totalNull = false;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode curr = q.poll();
if (curr.left != null) {
if (totalNull)
return false;
q.offer(curr.left);
}
else if (curr.left == null) {
totalNull = true;
}
if (curr.right != null) {
if (totalNull)
return false;
q.offer(curr.right);
}
else if (curr.right == null) {
totalNull = true;
}
}
}
return true;
}
自己写出来的。
可以参考下下面两个网页：
http://www.geeksforgeeks.org/check-if-a-given-binary-tree-is-complete-tree-or-not/
http://www.geeksforgeeks.org/check-whether-binary-tree-complete-not-set-2-recursive-solution/
Anyway, Good luck, Richardo!
My code:
/**
* 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 h = height(root);
if (h == -1) {
return 0;
}
else {
int right = height(root.right);
if (right == h - 1) {
return (1 << h) + countNodes(root.right);
}
else {
return (1 << (h - 1)) + countNodes(root.left);
}
}
}
private int height(TreeNode root) {
if (root == null) {
return -1;
}
return 1 + height(root.left);
}
}
这道题目我的做法超时了，即使换成 比特移位操作。
然后看了答案，觉得还是醍醐灌顶。
做大的变化在于右子树。
右子树高度和左子树之差，可能是0，可能是1
当差是0， 那么左子树一定会complete，那么我们可以用公式先计算出 左子树 + 根节点个数，然后recursion计算，右子树结点个数
当差是1，那么，右子树一定是complete tree，只不过高度少了1，移位的时候，少向右移动移位即可。然后我们需要recursive计算出，左子树的结点个数。
差不多就这么个思路。
iteration的做法也是如此：
My code:
/**
* 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 h = height(root);
int ret = 0;
while (root != null) {
int right = height(root.right);
if (right == h - 1) {
ret += (1 << h);
root = root.right;
}
else {
ret += (1 << (h - 1));
root = root.left;
}
h--;
}
return ret;
}
private int height(TreeNode root) {
if (root == null) {
return -1;
}
return 1 + height(root.left);
}
}
reference:
https://discuss.leetcode.com/topic/15533/concise-java-solutions-o-log-n-2
上一下我写的TLE的解法：
My code：
/**
* 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;
}
return helper(root);
}
private int helper(TreeNode root) {
if (root == null) {
return 0;
}
int left = getMaxDepth(root.left);
int right = getMinDepth(root.right);
if (left == right) {
return (1 << (left + 1)) - 1;
}
else {
int leftMin = getMinDepth(root.left);
if (left == leftMin) {
return (1 << left) + helper(root.right);
}
else {
return helper(root.left) + 1 + helper(root.right);
}
}
}
private int getMaxDepth(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(getMaxDepth(root.left), getMaxDepth(root.right)) + 1;
}
private int getMinDepth(TreeNode root) {
if (root == null) {
return 0;
}
else {
return Math.min(getMinDepth(root.left), getMinDepth(root.right)) + 1;
}
}
}
如何判断一棵树是否为complete？
就判断 左子树的最大深度和右子树的最小深度是否相等。
如果相等，就是complete
Anyway, Good luck, Richardo! -- 09/07/2016
