算法训练营day13 | {226.翻转二叉树, 101.对称二叉树, 104.二叉树的最大深度, 111.二叉树的最小深度}

第六章二叉树part02，体会不同的题目适用于不同的遍历方式，先思考递归做法，接着是迭代法。

226. 翻转二叉树

• 题目链接：226. 翻转二叉树
• 文档讲解：代码随想录–226. 翻转二叉树
• 视频讲解：听说一位巨佬面Google被拒了，因为没写出翻转二叉树 | LeetCode：226.翻转二叉树
• 状态：昨天刷了很多层序遍历（BFS）的题，这题也可以用层序遍历解决。

1.1 看完视频的想法

• 前序/后序遍历都能解决这个问题，遍历到哪个节点，本层递归要做的是交换这个节点的左右孩子，画图跟一下遍历就想清楚了。

1.2 解法总结

• 层序遍历（BFS）

  ▶

  226. 翻转二叉树

  class Solution {
      public TreeNode invertTree(TreeNode root) {
          Deque<TreeNode> queue = new ArrayDeque<>();
          if(root != null) queue.offerLast(root);
          while (!queue.isEmpty()) {
              int size = queue.size();
              while (size-- > 0) {
                  TreeNode node = queue.pollFirst();
                  swap(node);
                  if(node.left != null) queue.offerLast(node.left);
                  if(node.right != null) queue.offerLast(node.right);
              }
          }
          return root;
      }
      public void swap(TreeNode node) {
          TreeNode tmp = node.left;
          node.left = node.right;
          node.right = tmp;
      }
  }

• 前序遍历（DFS）–递归法

  ▶

  226. 翻转二叉树

  class Solution {
      public TreeNode invertTree(TreeNode root) {
          if(root == null) return null;
          swapChildren(root);
          invertTree(root.left);
          invertTree(root.right);
          return root;
      }
      
      public void swapChildren(TreeNode node) {
          TreeNode tmp = node.left;
          node.left = node.right;
          node.right = tmp;
      }
  }

• 前序遍历（DFS）–迭代法

  ▶

  226. 翻转二叉树

  class Solution {
      public TreeNode invertTree(TreeNode root) {
          Deque<TreeNode> stack = new ArrayDeque<>();
          if(root != null) stack.offerFirst(root);
          while(!stack.isEmpty()) {
              TreeNode node = stack.pollFirst();
              swapChildren(node);
              if(node.right != null) stack.offerFirst(node.right);
              if(node.left != null) stack.offerFirst(node.left);
          }
          return root;
      }
  
      public void swapChildren(TreeNode node) {
          TreeNode tmp = node.left;
          node.left = node.right;
          node.right = tmp;
      }
  }

101. 对称二叉树

• 题目链接：101. 对称二叉树
• 文档讲解：代码随想录–101. 对称二叉树
• 视频讲解：新学期要从学习二叉树开始！ | LeetCode：101. 对称二叉树
• 状态：检查一个二叉树是否是镜像对称的，就要判断这个二叉树是可以反转的。看了一会没思路。

2.1 看完视频的想法

• 要判断一个二叉树是否可以反转，需要比较左子树的外侧节点和右子树的外侧节点是否相同、左子树的内侧节点和右子树的内侧节点是否相同，然后把这个信息返回给该子树的根节点，让根节点知道它的子树是否是镜像对称，这道题适用于后序遍历，并且在递归遍历的过程中，要同时遍历左（左右中）、右（右左中）两个子树哦。
  

2.2 递归法

• 再次梳理一遍递归三部曲，把逻辑分析清楚。

1. 确定递归函数的参数和返回值
   • 因为我们要比较的是根节点的两个子树是否是可以相互反转的，进而判断这个树是不是对称树，所以要比较的是两个树，参数自然也是左子树节点和右子树节点。
   • 返回值是boolean
2. 确定终止的条件
   • 先把左、右节点为空的情况讨论清楚，再来分析都不为空、但值不相同的情况，自然不会造成空指针异常。
3. 确定单层递归的逻辑
   • 此时才进入单层递归的逻辑，就是处理左右节点都不为空、并且数值相同的情况。
     • 比较两个子树外侧的节点是否对称；
     • 比较内侧的节点是否对称；
     • 都对称则返回true，否则返回false。

▶

101. 对称二叉树

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return compare(root.left, root.right);
    }

    public boolean compare(TreeNode left, TreeNode right) {
        if(left == null && right != null) return false;
        else if (left != null && right == null) return false;
        else if (left == null && right == null) return true;
        else if (left.val != right.val) return false;
        
        boolean outside = compare(left.left, right.right);
        boolean inside = compare(left.right, right.left);
        return outside && inside;
    }
}

2.3 迭代法

• 本题的本质是判断两个树是否是相互翻转的，其实已经不是所谓二叉树遍历的前后序的迭代写法了。

• （看题解之后）我们可以使用队列来比较两个树（根节点的左右子树）是否相互翻转。
  

• 在定义一个双端队列的实现类时，在Java中，ArrayDeque不允许存null！！！改用LinkedList作为Deque。

• 迭代法–双端队列数据结构，相当于两个栈

  ▶

  101. 对称二叉树

  class Solution {
      public boolean isSymmetric(TreeNode root) {
          Deque<TreeNode> deque = new LinkedList<>();
          deque.offerFirst(root.left);
          deque.offerLast(root.right);
          while(!deque.isEmpty()) {
              TreeNode left = deque.pollFirst();
              TreeNode right = deque.pollLast();
              if (left == null && right == null) continue;
              if(left == null || right == null || left.val != right.val) return false;
              deque.offerFirst(left.left);
              deque.offerFirst(left.right);
              deque.offerLast(right.right);
              deque.offerLast(right.left);
          }
          return true;
      }
  }

• 迭代法–普通队列数据结构

  ▶

  101. 对称二叉树

  class Solution {
      public boolean isSymmetric(TreeNode root) {
          Deque<TreeNode> deque = new LinkedList<>();
          deque.offerLast(root.left);
          deque.offerLast(root.right);
          while(!deque.isEmpty()) {
              TreeNode left = deque.pollFirst();
              TreeNode right = deque.pollFirst();
              if (left == null && right == null) continue;
              if(left == null || right == null || left.val != right.val) return false;
              deque.offerLast(left.left);
              deque.offerLast(right.right);
              deque.offerLast(left.right);
              deque.offerLast(right.left);
          }
          return true;
      }
  }

2.4 相关题目

• 在root的某个子节点处，是否存在一棵树整体结构和值都与subroot完全相同。这其实是两个问题：
  1. 在root中找一个起点;
  2. 从这个起点开始，判断两颗树是否完全相同。
• 子树问题 = 找起点 + 判等树; 这两个逻辑，绝对不能写在同一个递归里。

▶

572. 另一棵树的子树

// 主函数负责找起点
// 辅助函数负责比较两棵树是否相同
// 子树问题=找起点+判等树 这两个逻辑一定要拆分，明确递归的职责！
class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) return false;
        // 以当前结点为根结点尝试匹配
        if (isSameTree(root, subRoot)) return true;
        
        // 否则继续去左右子树找起点
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    public boolean isSameTree(TreeNode a, TreeNode b) {
        if (a == null && b != null) return false;
        else if (a != null && b == null) return false;
        else if (a == null && b == null) return true;
        else if (a.val != b.val) return false;

        return isSameTree(a.left, b.left) && isSameTree(a.right, b.right);
    }
}

104. 二叉树的最大深度

• 题目链接：104. 二叉树的最大深度
• 文档讲解：代码随想录–104. 二叉树的最大深度
• 视频讲解：二叉树的高度和深度有啥区别？究竟用什么遍历顺序？很多录友搞不懂 | 104.二叉树的最大深度
• 状态：昨天用层序遍历过了这题。

3.1 看完视频的想法

• 什么是深度，什么是高度，如何求深度，如何求高度，这里有关系到二叉树的遍历方式。
  • 深度：某个节点到根节点的距离
  • 高度：某个节点到叶子节点的距离
  • 如何求深度：前序遍历的方式一路向下搜索
  • 如何求高度：后序遍历，左右中，反馈给父节点子树的高度
  • 根节点的高度 = 一棵树的最大深度
• 一道题，适合用什么遍历方式要自己思考，本题如果采用求高度的做法，从下往上需要返回信息给父节点，那么单层递归的逻辑就适合用后序遍历。

3.2 解法总结

• 后序遍历–递归法

  ▶

  104. 二叉树的最大深度

  class Solution {
      public int maxDepth(TreeNode root) {
          if(root == null) return 0;
          int leftHeight = maxDepth(root.left);
          int rightHeight = maxDepth(root.right);
          return 1 + Math.max(leftHeight, rightHeight);
      }
  }

• 前序遍历–递归法，有回溯的思想

  ▶

  104. 二叉树的最大深度

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

• 层序遍历（BFS）

  ▶

  104. 二叉树的最大深度

  class Solution {
      public int maxDepth(TreeNode root) {
          int maxDepth = 0;
          Deque<TreeNode> queue = new ArrayDeque<>();
          if(root != null) queue.offerLast(root);
          while(!queue.isEmpty()) {
              int size = queue.size();
              while(size-- > 0) {
                  TreeNode node = queue.pollFirst();
                  if(node.left != null) queue.offerLast(node.left);
                  if(node.right != null) queue.offerLast(node.right);
              }
              maxDepth++;
          }
          return maxDepth;
      }
  }

111. 二叉树的最小深度

• 题目链接：111. 二叉树的最小深度
• 文档讲解：代码随想录–111. 二叉树的最小深度
• 视频讲解：看起来好像做过，一写就错！ | LeetCode：111.二叉树的最小深度
• 状态：层序遍历也可以解决这题，但递归做法我还没想过。

4.1 看完视频的想法

• 本题依然采用后序遍历的做法，求高度，把根节点传入函数，即可求根节点到叶子节点的最小距离。但这里要注意有坑，只有左右子树都为空，即到达叶子节点的时候，才是最小深度。

4.2 解法总结

• 后序遍历–递归法

  ▶

  111. 二叉树的最小深度

  class Solution {
      public int minDepth(TreeNode root) {
          if (root == null) return 0;
          int leftHeight = minDepth(root.left);
          int rightHeight = minDepth(root.right);
          if(root.left == null && root.right != null) return 1 + rightHeight;
          else if (root.left != null && root.right == null) return 1 + leftHeight;
          return 1 + Math.min(leftHeight, rightHeight);
      }
  }

• 层序遍历（BFS）

  ▶

  111. 二叉树的最小深度

  class Solution {
      public int minDepth(TreeNode root) {
          int minDepth = 0;
          Deque<TreeNode> queue = new ArrayDeque<>();
          if(root != null) queue.offerLast(root);
          while(!queue.isEmpty()) {
              int size = queue.size();
              while(size-- > 0) {
                  TreeNode node = queue.pollFirst();
                  if(node.left == null && node.right == null) {
                      while (!queue.isEmpty()) queue.pollFirst();
                      break;
                  }
                  if(node.left != null) queue.offerLast(node.left);
                  if(node.right != null) queue.offerLast(node.right);
              }
              minDepth++;
          }
          return minDepth;
      }
  }

5. 今日收获

• 遍历节点的顺序和处理节点的顺序是否一致，不一致要引入指针辅助遍历。
• 什么样的题目适合什么样的遍历方式，这一点我开始慢慢找到感觉了，前序、中序、后序遍历，解题的过程中多思考用的什么遍历方式，为什么用这个遍历方式。
• 关于Java API，双端队列的实现类ArrayDeque中不能存储null.
• 数组、链表、字符串有反转题，今天二叉树也有反转题，真是妙啊。
• 学习时长：4小时