Count Complete Tree Nodes

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.

递归树高法

复杂度

时间 O(N) 空间 O(1)

思路

完全二叉树的一个性质是，如果左子树最左边的深度，等于右子树最右边的深度，说明这个二叉树是满的，即最后一层也是满的，则以该节点为根的树其节点一共有2^h-1个。如果不等于，则是左子树的节点数，加上右子树的节点数，加上自身这一个。

注意

• 这里在左节点递归时代入了上次计算的左子树最左深度减1，右节点递归的时候代入了上次计算的右子树最右深度减1，可以避免重复计算这些深度

• 做2的幂时不要用Math.pow，这样会超时。用1<<height这个方法来得到2的幂

代码

public class Solution {    public int countNodes(TreeNode root) {        return countNodes(root, -1, -1);    }        private int countNodes(TreeNode root, int lheight, int rheight){        // 如果没有上轮计算好的左子树深度，计算其深度        if(lheight == -1){lheight = 0;TreeNode curr = root;while(curr != null){    lheight++;    curr = curr.left;}        }        // 如果没有上轮计算好的右子树深度，计算其深度        if(rheight == -1){rheight = 0;TreeNode curr = root;while(curr != null){    rheight++;    curr = curr.right;}        }        // 如果两个深度一样，返回2^h-1        if(lheight == rheight) return (1 << lheight) - 1;        // 否则返回左子树右子树节点和加1        return 1 + countNodes(root.left, lheight - 1, -1) + countNodes(root.right, -1, rheight - 1);    }}

迭代树高法

复杂度

时间 O(N) 空间 O(1)

思路

用迭代法的思路稍微有点不同，因为不再是递归中那样的分治法，我们迭代只有一条正确的前进方向。所以，我们判断的时左节点的最左边的深度，和右节点的最左边深度。因为最后一层结束的地方肯定在靠左的那侧，所以我们要找的就是这个结束点。如果两个深度相同，说明左子树和右子树都是满，结束点在右侧，如果右子树算出的最左深度要小一点，说明结束点在左边，右边已经是残缺的了。根据这个大小关系，我们可以确定每一层的走向，最后找到结束点。另外，还要累加每一层的节点数，最后如果找到结束点，如果结束点是左节点，就多加1个，如果结束点是右节点，就多加2个。

注意

• 同样的，记录上次计算的最左深度，可以减少一些重复计算

• 用int记录上次最左深度更快，用Integer则会超时

代码

未优化版本

public class Solution {    public int countNodes(TreeNode root) {        int res = 0;        Integer lheight = null, rheight = null;        while(root != null){// 得到左节点的最左深度int leftH = getH(root.left);// 得到右节点的最左深度int rightH = getH(root.right);// 左节点的最左深度大，说明右边已经残缺，结束点在左边if(leftH > rightH){    if(rightH != 0) res += 1 << rightH;    else return res + 2;    root = root.left;// 否则说明结束点在右边} else {    if(leftH != 0) res += 1 << leftH;    else return res + 1;    root = root.right;}        }        return res;    }        private int getH(TreeNode root){        int h = 0;        while(root != null){++h;root = root.left;        }        return h;    }}public class Solution {    public int countNodes(TreeNode root) {        int res = 0;        int lheight = -1, rheight = -1;        while(root != null){// 如果没有上次记录的左边最左深度，重新计算if(lheight == -1){    TreeNode curr = root.left;    lheight = 0;    while(curr != null){        curr = curr.left;        lheight++;    }    }// 如果没有上次记录的右边最左深度，重新计算if(rheight == -1){    TreeNode curr = root.right;    rheight = 0;    while(curr != null){        curr = curr.left;        rheight++;    }}// 深度相同，说明结束点在右边if(lheight == rheight){    // 如果是不是最后一个节点，累加这一层的节点    if(lheight != 0){        res += 1 << lheight;    } else {    // 如果是最后一个节点，结束点在右边意味着右节点是缺失的，返回res+1        return res + 1;    }    root = root.right;    lheight = rheight - 1;    rheight = -1;// 否则结束点在左边} else {    // 如果是不是最后一个节点，累加这一层的节点    if(rheight != 0){        res += 1 << rheight;    } else{    // 如果是最后一个节点，返回res+2        return res + 2;    }    root = root.left;    lheight = lheight - 1;    rheight = -1;}        }        return res;    }}