LeetCode刷题——完全二叉树的节点个数#222#Medium

完全二叉树的节点个数的思路探讨与源码
    完全二叉树的节点个数的题目如下图，该题属于搜索类和树类型的题目，主要考察对于搜索方法的使用和树结构的理解。本文的题目作者想到2种方法，分别是二分搜索方法和DFS深度优先搜索方法，其中二分搜索方法使用Java进行编写，而DFS深度优先搜索方法使用Python进行编写，当然这可能不是最优的解法，还希望各位大佬给出更快的算法。

    本人认为该题目可以使用二分搜索方法的思路进行解决，首先判断这个树是否为空，如果是就直接返回0的结果。然后开始对当前节点的左右子节点分别进行计算，在计算函数内部是去判断树是否不为空，如果是就将结果加1并继续访问左边的节点，直到访问结束并返回计数结果。在计算函数返回结果后，判断左边和右边的节点个数是否相等，如果相等就将左子树的计算结果左移1位并添加到右子树递归计算的结果里面继续迭代；如果不相等就将右子树的计算结果左移1位并添加到左子树递归计算的结果里面继续迭代。如此进行直到最终递归结束并返回结果。那么按照这个思路我们的Java代码如下：

#喷火龙与水箭龟
class Solution {
    public int countNodes(TreeNode root) {
        if(root == null){
           return 0;
        } 
        int rightNum = countFun(root.right);
        int leftNum = countFun(root.left);
        if(rightNum == leftNum){
            return countNodes(root.right) + (1<<leftNum);
        }else{
            return countNodes(root.left) + (1<<rightNum);
        }
    }
    private int countFun(TreeNode root){
        int ind = 0;
        while(root != null){
            ind = ind + 1;
            root = root.left;
        }
        return ind;
    }
}

    显然，我们看到二分搜索的方法效果非常好，同时还可以使用DFS深度优先搜索方法解决。首先判断这个树是否为空，如果是空就直接返回0的结果，然后继续访问左右节点，并将结果加1，对于下一层的左右节点各自进行递归搜索，直到搜索结束并返回最终的节点个数结果。所以按照这个思路就可以解决，下面是Python代码：

#喷火龙与水箭龟
class Solution:
    def __init__(self):
        self.res = 0
    def countNodes(self, root: TreeNode) -> int:
        if(not root):
            return 0
        self.res = self.res + 1
        self.countNodes(root.left)
        self.countNodes(root.right)
        return self.res

    从结果来说Java版本二分搜索方法的效率比较好，而Python版本的DFS深度优先搜索方法的速度比较一般，但应该是有更多的方法可以进一步提速的，希望朋友们能够多多指教，非常感谢。