leetcode 222. Count Complete Tree Nodes 计算满二叉树的节点数量 + DFS深度优先遍历 + 公式计算

ゝ一纸荒年。 2022-06-08 11:57 87阅读 0赞

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.

满二叉树的节点数量的求解，直接遍历必然超时，所里判断是否是满二叉子树来做。

**直接深度优先遍历DFS会超时，所以可以使用公式来计算，这个利用了满二叉树的性质**

代码如下：

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

下面是C++的做法，就是做一个DFS深度优先搜索找到满二叉树，然后使用公式直接计算，否则递归计算

**注意位运算的计算符号的优先级是低于普通的加减乘除运算的**

代码如下：

#include <iostream>
    #include <algorithm>
    #include <vector>
    #include <set>
    #include <map>
    
    using namespace std;
    
    /*
    struct TreeNode 
    {
         int val;
         TreeNode *left;
         TreeNode *right;
         TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    */
    
    class Solution 
    {
    public:
        int countNodes(TreeNode* root)
        {
            if (root == NULL)
                return 0;
            else
            {
                int leftDepth = getLeftDepth(root);
                int rightDepth = getRightDepth(root);
                if (leftDepth == rightDepth)
                    return (2 << (leftDepth - 1)) - 1;
                else
                    return countNodes(root->left) + countNodes(root->right) + 1;
            }
        }
    
        int getLeftDepth(TreeNode* root)
        {
            int count = 0;
            while (root != NULL)
            {
                count++;
                root = root->left;
            }
            return count;
        }
    
        int getRightDepth(TreeNode* root)
        {
            int count = 0;
            while (root != NULL)
            {
                count++;
                root = root->right;
            }
            return count;
        }
    };