算法训练day16 LeetCod 104.111.222

104.二叉树的最大深度

题目

104. 二叉树的最大深度 - 力扣（LeetCode）

题解

代码随想录 (programmercarl.com)

递归采用后序的遍历顺序，在根节点处做高度数据的处理

class Solution
{
public:
    int getdepth(TreeNode *node)
    {
        if (node == NULL)
            return 0;
        int left = getdepth(node->left);
        int right = getdepth(node->right);
        int depth = max(left, right) + 1;
        return depth;
    }
    int maxDepth(TreeNode *root)
    {
        return getdepth(root);
    }
};

111.二叉树的最小深度

题目

111. 二叉树的最小深度 - 力扣（LeetCode）

题解

代码随想录 (programmercarl.com)

类似上一题，但是注意单支子树结点为空的情况

class Solution
{
public:
    int getdepth(TreeNode *node)
    {
        if (node == NULL)
            return 0;
        int left = getdepth(node->left);
        int right = getdepth(node->right);
        if (node->left == NULL && node->right != NULL)
            return right + 1;
        if (node->left != NULL && node->right == NULL)
            return left + 1;
        int result = min(left, right) + 1;
        return result;
    }
    int minDepth(TreeNode *root)
    {
        return getdepth(root);
    }
};

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

题目

222. 完全二叉树的节点个数 - 力扣（LeetCode）

题解

代码随想录 (programmercarl.com)

遍历，在根结点处处理数据

class Solution
{
public:
    int getNodeNum(TreeNode *node)
    {
        if (node == NULL)
            return 0;
        int left = getNodeNum(node->left);
        int right = getNodeNum(node->right);
        int result = left + right + 1;
        return result;
    }

    int countNodes(TreeNode *root)
    {
        return getNodeNum(root);
    }
};