算法训练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);
      }
  };