222.Count Complete Tree Nodes(Medium)
LanyuanXiaoyao's Blog ヽ(✿゚▽゚)ノ

222.Count Complete Tree Nodes(Medium)


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.

  难度在于其如何优化递归,缩短递归的次数

My Solution

(Java) Version 1 Time: Time Limit Exceeded:

  遍历一个树,最先想到的方法果然是递归,随手就可以写出一个最简单的递归遍历,当然,不出意外的话,这是一定会超时的,果然就超时了,只是写法很容易理解,留在这里作为纪念,其次是想说,无脑没有优化的递归确实是相当慢

/**
 * 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;
        }
        else{
            return 1+countNodes(root.left)+countNodes(root.right);
        }
    }
}

(Java) Version 2 Time: 111ms:

  这里真的是日了dog了,我只能说向位运算低头,原来用Math.pow()来计算满二叉树的几点,然后就超时了,换成«之后就赤果果地过了,我的天……   好了,说一下思路,直接遍历每一个节点是不现实的,所以必须通过完全二叉树的特点来计算,我们可以想到,除了最下的那一层,其余的部分,都是满二叉树,这样我们首先可以判断当前的二叉树是不是满二叉树,判断的方法是判断树最左和最右两边的长度是否相等,如果相等就可以直接计算,如果不等就进入递归,分别计算左右两颗子树,知道只有一个节点的时候就停止。   因为完全二叉树进行左右分割之后,很容易就会出现满二叉树,所以节省了大量的遍历节点的时间

/**
 * 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 count_left = count_length_l(root);
        int count_right = count_length_r(root);
        if(root == null){
            return 0;
        }
        else{
            if(count_left == count_right){
                return (1 << count_left)-1;
            }
            else{
                return countNodes(root.left)+countNodes(root.right)+1;
            }
        }
    }

    public int count_length_l(TreeNode root){
        int count = 0;
        while(root!=null){
            count++;
            root = root.left;
        }
        return count;
    }

    public int count_length_r(TreeNode root){
        int count = 0;
        while(root!=null){
            count++;
            root = root.right;
        }
        return count;
    }
}

(Java) Version 3 Time: 79ms:

  事实上上面那个方法就已经过了的,不过当时没有想到位运算,所以以为是遍历的时间太长,于是重新写了下面的这个方法,时间果然快很多,当然如果没有位运算还是会超时。   思路是把二叉树分为左边一颗子树和右边一颗子树,分别计算两棵树的最左边,然后比较,如果相等的话,就表明左边的子树是满二叉树(是不是很巧妙),如果不等的话,就表明右边的子树是满二叉树(想一下满二叉树的结构),然后分别进入递归就行了,我没有认真计算时间复杂度,但是从巧妙程度来看应该是比上面的方法快的

/**
 * 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 count_left = count_length(root.left);
        int count_right = count_length(root.right);
        if(count_left == count_right){
            return (1 << count_left)+countNodes(root.right);
        }
        else{
            return (1 << count_right)+countNodes(root.left);
        }
    }
    
    public int count_length(TreeNode root){
        int count = 0;
        while(root!=null){
            count++;
            root = root.left;
        }
        return count;
    }
}

  很高兴的一点是,我自己写的两种遍历方式似乎就已经是discuss中的两大主流方法了,基本上他们的方法也是这两种实现,只是写法有一点不同……所以下面贴了一个最详细的大神的多种解法,好像挺有意思的……

(Java) Version 4 Time: 102ms (By StefanPochmann):

  简短一直都是推崇的原因之一

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int height(TreeNode root) {
        return root == null ? -1 : 1 + height(root.left);
    }
    public int countNodes(TreeNode root) {
        int h = height(root);
        return h < 0 ? 0 :
               height(root.right) == h-1 ? (1 << h) + countNodes(root.right)
                                         : (1 << h-1) + countNodes(root.left);
    }
}

(Java) Version 5 Time: 63ms (By StefanPochmann):

  果然一旦摆脱了递归之后速度就扶摇直上,这个是一个迭代的实现方式,确实需要好好学习一下如何把递归转化为迭代实现……

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int height(TreeNode root) {
        return root == null ? -1 : 1 + height(root.left);
    }
    public int countNodes(TreeNode root) {
        int nodes = 0, h = height(root);
        while (root != null) {
            if (height(root.right) == h - 1) {
                nodes += 1 << h;
                root = root.right;
            } else {
                nodes += 1 << h-1;
                root = root.left;
            }
            h--;
        }
        return nodes;
    }
}

(Java) Version 6 Time: 75ms (By StefanPochmann):

  中间循环的实现原理还没有细看,应该是把高度方法放进了一个方法里面,其中的整合还有待琢磨,应该有其中的巧妙之处

/**
 * 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;
        TreeNode left = root, right = root;
        int height = 0;
        while (right != null) {
            left = left.left;
            right = right.right;
            height++;
        }
        if (left == null)
            return (1 << height) - 1;
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}

评论