day16

1、104.二叉树的最大深度

1. 递归法

   1. 二叉树的最大深度 ==》根节点的高度

      1. 通过后序（左右中）求得根节点高度来求得二叉树最大深度。
      2. 递归三要素
         1. 确定递归函数的参数和返回值：参数就是传入树的根节点，返回就返回这棵树的深度，所以返回值为int类型。
         2. 确定终止条件：如果为空节点的话，就返回0，表示高度为0。
         3. 确定单层递归的逻辑：先求它的左子树的深度，再求右子树的深度，最后取左右深度最大的数值 再+1 （加1是因为算上当前中间节点）就是目前节点为根节点的树的深度。

   2. 代码实现

      class Solution {
          public int maxDepth(TreeNode root) {
              return getDepth(root);
          }
      
          public int getDepth(TreeNode node){
              if(node == null){
                  return 0;
              }
      
              int leftDepth = getDepth(node.left);
              int rightDepth = getDepth(node.right);
              int depth = Math.max(leftDepth, rightDepth) + 1;
      
              return depth;
          }
      
      }
      

2. 迭代法

   1. 套用二叉树层序遍历模板

   2. 代码实现

      class Solution {
          public int maxDepth(TreeNode root) {
              Queue<TreeNode> que = new LinkedList<TreeNode>();
              int depth = 0;
      
              if(root != null){
                  que.offer(root);
              }
      
              while(!que.isEmpty()){
                  int size = que.size();
                  depth++; //记录层数
      
                  for(int i=0; i<size; i++){
                      TreeNode node = que.poll();
                      if(node.left != null){
                          que.offer(node.left);
                      }
                      if(node.right != null){
                          que.offer(node.right);
                      }
                  }
              }
              return depth;
          }
      }
      

2、559.n叉树的最大深度

1. 递归法

   1. 代码实现

      class Solution {
           public int maxDepth(Node root) {
               return getDepth(root);
           }
      
           public int getDepth(Node node){
               if(node == null){
                   return 0;
               }
      
               int depth = 0;
               for(int i=0; i<node.children.size(); i++){
                   int childDepth = getDepth(node.children.get(i));
                   depth = Math.max(childDepth, depth);
               }
      
               return depth+1; 
           }
       }
      

2. 迭代法

   1. 代码实现

      class Solution {
          public int maxDepth(Node root) {
              if(root == null){
                  return 0;
              }
      
              Queue<Node> que = new LinkedList<Node>();
              int depth = 0;
              que.offer(root);
      
      
              while(!que.isEmpty()){
                  int size = que.size();
                  depth++;
      
                  for(int i=0; i<size; i++){
                      Node node = que.poll();
                      for(int j=0; j<node.children.size(); j++){
                          que.offer(node.children.get(j));
                      }
                  }
              }
      
              return depth;
          }
      }
      

3、111.二叉树的最小深度

1. 注意：最小深度是从根节点到最近叶子节点的最短路径上的节点数量

   1. 叶子节点是指左右孩子节点均为空的节点

2. 递归法

   1. 递归三部曲

      1. 参数为要传入的二叉树根节点，返回的是int类型的深度。

      2. 确定终止条件：遇到空节点返回0，表示当前节点的高度为0。

      3. 确定单层递归的逻辑：

         如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。

         反之，右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。

         最后如果左右子树都不为空，返回左右子树深度最小值 + 1 。

      4. 注意：遍历的顺序为后序（左右中），可以看出：求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。

   2. 代码实现

      class Solution {
          public int minDepth(TreeNode root) {
              return getDepth(root);
          }
      
          public int getDepth(TreeNode node) {
              if(node == null){
                  return 0;
              }
      
              int leftDepth = getDepth(node.left); //左
              int rightDepth = getDepth(node.right); //右
      												//中
              // 当一个左子树为空，右不为空，这时并不是最低点
              if(node.left == null && node.right != null){
                  return rightDepth + 1;
              }
              // 当一个右子树为空，左不为空，这时并不是最低点
              if(node.left != null && node.right == null){
                  return leftDepth + 1;
              }
      
              int depth = 1 + Math.min(leftDepth, rightDepth);
              return depth;
              
          }
      }
      

3. 迭代法

   1. 套用层序遍历模板

      class Solution {
          public int minDepth(TreeNode root) {
              Queue<TreeNode> que = new LinkedList<TreeNode>();
              int depth = 0;
      
              if(root != null){
                  que.offer(root);
              }
      
              while(!que.isEmpty()){
                  int size = que.size();
                  depth++;
      
                  for(int i=0; i<size; i++){
                      TreeNode node = que.poll();
                      if(node.right==null && node.left==null){ //遍历到叶子节点
                          return depth;
                      }
                      if(node.left != null){
                          que.offer(node.left);
                      }
                      if(node.right != null){
                          que.offer(node.right);
                      }
                  }
              }
              return depth;
          }
      }
      

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

1. 递归法

   1. 递归三部曲

      1. 确定递归函数的参数和返回值：参数就是传入树的根节点，返回就返回以该节点为根节点二叉树的节点数量，所以返回值为int类型
      2. 确定终止条件：如果为空节点的话，就返回0，表示节点数为0
      3. 确定单层递归的逻辑：先求它的左子树的节点数量，再求右子树的节点数量，最后取总和再加一 （加1是因为算上当前中间节点）就是目前节点为根节点的节点数量

   2. 代码实现

      class Solution {
          public int countNodes(TreeNode root) {
              return getCount(root);
          }
      
          public int getCount(TreeNode node){
              if(node == null){
                  return 0;
              }
      
              int leftCount = getCount(node.left);
              int rightCount = getCount(node.right);
              int count = leftCount + rightCount + 1;
              return count;
          }
      }
      

2. 迭代法

   1. 套用层序遍历的模板

      class Solution {
          public int countNodes(TreeNode root) {
              if(root == null){
                  return 0;
              }
      
              Queue<TreeNode> que = new LinkedList<TreeNode>();
              int count = 0;
      
              que.offer(root);
      
              while(!que.isEmpty()){
                  int size = que.size();
                  for(int i=0; i<size; i++){
                      TreeNode node = que.poll();
                      count++; //记录节点个数
                      if(node.left != null){
                          que.offer(node.left);
                      }
                      if(node.right != null){
                          que.offer(node.right);
                      }
                  }
              }
      
              return count;
      
          }
      }