LintCode，c++算法笔记(容易级7.31)

（一）给定一个二叉树，找出其最小深度。

二叉树的最小深度为根节点到最近叶子节点的距离。

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 * int val;
 * TreeNode *left, *right;
 * TreeNode(int val) {
 * this->val = val;
 * this->left = this->right = NULL;
 * }
 * }
 */
class Solution {
public:
/**
 * @param root: The root of binary tree.
 * @return: An integer
 */
    int minDepth(TreeNode *root) {
        int minleft,minright=0;
if(root==NULL)
        {
return 0;
        }
if (root->left == NULL && root->right == NULL) return 1;
if (root->left == NULL) return minDepth(root->right) + 1;
else if (root->right == NULL) return minDepth(root->left) + 1;
else return 1 + min(minDepth(root->left), minDepth(root->right));
    }
};

（二）计算在一个 32 位的整数的二进制表示中有多少个 1.

class Solution {
public:
/**
 * @param num: an integer
 * @return: an integer, the number of ones in num
 */
    int countOnes(int num) {
       int count = 0;
while(num)
       {
           num = num & (num - 1);
           count++;
       }
return count;
    }
};

（三）用 O(1) 时间检测整数 n 是否是 2 的幂次。

class Solution {
public:
/*
 * @param n: An integer
 * @return: True or false
 */
    bool checkPowerOf2(int n) {
if(n<0)
        {
return false;
        }
if(countOnes(n)==1)
        {
return true;
        }
return false;
    }
int countOnes(int num) {
int count = 0;
while(num)
       {
           num = num & (num - 1);
count++;
       }
return count;
    }
};