对称二叉树

题目描述

力扣链接🔗

对称二叉树 - 图1

递归法分析

分成内外侧进行比较

对称二叉树 - 图2

递归的三大步：

  1. 确定递归函数的参数和返回值
    因为我们要比较的是根节点的两个子树是否是相互翻转的，进而判断这个树是不是对称树，所以要比较的是两个树，参数自然也是左子树节点和右子树节点。返回值自然是bool类型。
  2. 确定终止条件
    要比较两个节点数值相不相同，首先要把两个节点为空的情况弄清楚！否则后面比较数值的时候就会操作空指针了。
    节点为空的情况有：（注意我们比较的其实不是左孩子和右孩子，所以如下我称之为左节点右节点）
    • 左节点为空，右节点不为空，不对称，return false
    • 左不为空，右为空，不对称 return false
    • 左右都为空，对称，返回true
      此时已经排除掉了节点为空的情况，那么剩下的就是左右节点不为空：
    • 左右都不为空，比较节点数值，不相同就return false
      此时左右节点不为空，且数值也不相同的情况我们也处理了。
  3. 确定单层递归的逻辑
    此时才进入单层递归的逻辑，单层递归的逻辑就是处理 左右节点都不为空，且数值相同的情况。
    • 比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
    • 比较内测是否对称，传入左节点的右孩子，右节点的左孩子。
    • 如果左右都对称就返回true ，有一侧不对称就返回false 。

总的来说：
就是判断两个节点的四种情况：

  • 都为空，对称，返回true
  • 一空一不空，不对称
  • 两个取值不相等，不对称
  • 取值相等，但是孩子节点不一定相等，所以需要递归继续判断左右孩子，才能判断是否相等
  1. class Solution {
  2.     public boolean isSymmetric(TreeNode root) {
  3.         if (root == null) {
  4.             return true;
  5.         }
  6.         return compare(root.left, root.right);
  7.     }
  9.     /**
  10.      * 判断左右节点是否对称
  11.      *
  12.      * @param left
  13.      * @param right
  14.      * @return true表示对称，false表示不对称
  15.      */
  16.     boolean compare(TreeNode left, TreeNode right) {
  17.         if (left == null && right == null) return true; // 左右节点都为空，则是对称的
  18.         else if (left == null && right != null) return false;  // 左节点为空，右节点不为空，此时不对称
  19.         else if (left != null && right == null) return false;  // 左节点不为空，右节点为空，此时不对称
  20.         else if (left.val != right.val) return false;   // 左右节点的值不相等，此时不对称
  21.         else {  // 剩下的是左右节点相等的情况,此时递归判断孩子节点
  22.             boolean outside = compare(left.left, right.right); // 判断外侧
  23.             boolean inside = compare(left.right, right.left);  // 判断内侧
  24.             return inside && outside; // 如果该节点的左右孩子节点都是对称的，返回true
  25.         }
  26.     }
  27. }

使用队列和栈

使用队列的演示图：

通过队列来判断根节点的左子树和右子树的内侧和外侧是否相等。

对称二叉树 - 图3

  1.    /**
  2.      * 使用队列实现
  3.      *
  4.      * @param root
  5.      * @return
  6.      */
  7.     public boolean isSymmetric(TreeNode root) {
  8.         Queue<TreeNode> queue = new LinkedList<>(); // 辅助队列进行比较
  9.         if (root == null) {
  10.             return true;
  11.         }
  13.         queue.offer(root.left);
  14.         queue.offer(root.right);
  16.         while (!queue.isEmpty()) {
  17.             // 成对的取出元素进行判断
  18.             TreeNode leftNode = queue.poll();
  19.             TreeNode rightNode = queue.poll();
  21.             if (leftNode == null && rightNode == null) continue;    // 左右节点为空，为对称
  23.             if (leftNode == null && rightNode != null
  24.                     || leftNode != null && rightNode == null
  25.                     || leftNode.val != rightNode.val)
  26.                 return false;   // 三种情况为不对成
  28.             queue.offer(leftNode.left);     // 加入左节点左孩子
  29.             queue.offer(rightNode.right);   // 加入右节点右孩子
  30.             queue.offer(leftNode.right);    // 加入左节点右孩子
  31.             queue.offer(rightNode.left);    // 加入右节点左孩子
  32.         }
  34.         return true;
  35.     }
  36. }

将队列换成栈也可以实现，本质不变，都是成对的取出节点进行比较，再将孩子入栈或队列。

类似题目

相同的树

题目描述

力扣链接🔗

对称二叉树 - 图4

代码分析

比较两棵树，同时比较左侧和右侧。

  1. class Solution {
  2.     public boolean isSameTree(TreeNode p, TreeNode q) {
  3.         if (p == null && q == null) return true;
  4.         else if (p == null && q != null || p != null && q == null) return false;
  5.         else if (p.val != q.val) return false;
  6.         else {
  7.             // 注意此时不是比较内外侧，而是两棵树
  8.             boolean outside = isSameTree(p.left, q.left);   // 比较两棵树的左孩子
  9.             boolean inside = isSameTree(p.right, q.right);  // 比较两棵树的右孩子
  10.             return outside && inside;
  11.         }
  12.     }
  13. }

另一棵子树

题目描述

力扣链接🔗

对称二叉树 - 图5

代码分析

深度遍历每个节点，再将遍历的节点进行判断和subRoot是否相同即可。

  1. class Solution {
  3.     public boolean isSubtree(TreeNode root, TreeNode subRoot) {
  4.         if (root == null && subRoot == null) return true;
  5.         return dfs(root, subRoot);
  6.     }
  8.     /**
  9.          * 深度遍历判断
  10.          *
  11.          * @param root
  12.          * @param subRoot
  13.          * @return
  14.          */
  15.     public boolean dfs(TreeNode root, TreeNode subRoot) {
  16.         if (root == null) {
  17.             return false;
  18.         }
  20.         boolean curCompare = compare(root, subRoot);         // 先比较当前节点
  21.         boolean leftCompare = dfs(root.left, subRoot);      // 遍历左孩子
  22.         boolean rightCompare = dfs(root.right, subRoot);    // 遍历右孩子
  24.         return curCompare || rightCompare || leftCompare;
  25.     }
  27.     public boolean compare(TreeNode rootNode, TreeNode subRoot) {
  28.         if (rootNode == null && subRoot == null) {
  29.             return true;
  30.         }
  32.         if (rootNode == null && subRoot != null || subRoot == null && rootNode != null) {
  33.             return false;
  34.         }
  36.         if (rootNode.val != subRoot.val) {
  37.             return false;
  38.         }
  40.         return compare(rootNode.left, subRoot.left) && compare(rootNode.right, subRoot.right);
  41.     }
  42. }