算法随想Day14【二叉树】| LC104-二叉树的最大深度、LC111-二叉树的最小深度、LC222-完全二叉树的节点个数

深度

二叉树任意一个节点到根节点的距离（这条路径包含的节点数）

高度

二叉树任意一个节点到叶子节点的距离

LC104. 二叉树的最大深度

递归解法

int maxdepth(treenode* root)
{
    int leftdepth = 0, rightdepth = 0;
    if (root == null)
    {
        return 0;
    }
    leftdepth = maxdepth(root->left);
    rightdepth = maxdepth(root->right);
    int middledepth = max(leftdepth, rightdepth) + 1;
    return middledepth;
}

LC111. 二叉树的最小深度

注意：对图中这个二叉树，最小深度应该为“3”，即节点3到根节点1的距离。空节点是不能算深度的（如root的left孩子不存在，不能认为最小深度为1）。所以不能像上一道题一样，简单地将max替换成min。

递归解法

int maxdepth(treenode* root)
{
    int leftdepth = 0, rightdepth = 0;
    if (root == null)
    {
        return 0;
    }
    leftdepth = maxdepth(root->left);
    rightdepth = maxdepth(root->right);
    if (root->left == nullptr && root->right != nullptr)
    {
        return rightdepth + 1;
    }
    if (root->right == nullptr && root->left != nullptr)
    {
        return leftdepth + 1;
    }
    int middledepth = min(leftdepth, rightdepth) + 1;
    return middledepth;
}

LC222. 完全二叉树的节点个数

按照普通二叉树处理，时间复杂度和空间复杂度都是 O(n)

class Solution {
public:
    int count;
    int getnum(TreeNode* root, int count)
    {
        if (root == nullptr)
        {
            return 0;
        }
        int leftnum = getnum(root->left, count);
        int rightnum = getnum(root->right, count);
        int midnum = leftnum + rightnum + 1;
        return midnum;
    }

    int countNodes(TreeNode* root)
    {
        int count = 0;

        return getnum(root, count);
    }
};

Carl哥讲解，根据判断当前节点的左子树最左端和右子树最右端的深度是否相等，即可判断以当前节点为root的子树是否为满二叉树。时间复杂度O(logn*logn)，空间复杂度O(logn)。

int countNodes(TreeNode* root) {
    if (root == nullptr) return 0;
    TreeNode* left = root->left;
    TreeNode* right = root->right;
    int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的，为了下面求指数方便
    while (left) {  // 求左子树深度
        left = left->left;
        leftDepth++;
    }
    while (right) { // 求右子树深度
        right = right->right;
        rightDepth++;
    }
    if (leftDepth == rightDepth) {
        return (2 << leftDepth) - 1; // 注意(2<<1) 相当于2^2，所以leftDepth初始为0
    }
    return countNodes(root->left) + countNodes(root->right) + 1;
}

官方解法，使用“二分查找 + 位运算”，可达到时间复杂度O(logn)，空间复杂度O(1)