题目描述（简单难度）

101. Symmetric Tree - 图1

判断一个二叉树是否关于中心轴对称。

解法一

和 100 题 判断两个二叉树是否相等其实是一样的思路，都是用某种遍历方法来同时遍历两个树，然后看是否对应相等。

这里的需要遍历的两个树就是左子树和右子树了。

这里的对应相等的话，因为判断左子树 A 和右子树 B 是否对称，需要判断两点。

  • A 的根节点和 B 的根节点是否相等
  • A 的左子树和 B 的右子树是否相等，同时 A 的右子树和左子树是否相等。

上边两点都满足，就表示是对称的。所以代码就出来了。

  1. public boolean isSymmetric5(TreeNode root) {
  2.     if (root == null) {
  3.         return true;
  4.     }
  5.     return isSymmetricHelper(root.left, root.right);
  6. }
  8. private boolean isSymmetricHelper(TreeNode left, TreeNode right) {
  9.     //有且仅有一个为 null ，直接返回 false
  10.     if (left == null && right != null || left != null && right == null) {
  11.         return false;
  12.     }
  13.     if (left != null && right != null) 
  14.         //A 的根节点和 B 的根节点是否相等
  15.         if (left.val != right.val) {
  16.             return false;
  17.         }
  18.         //A 的左子树和 B 的右子树是否相等，同时 A 的右子树和左子树是否相等。
  19.         return isSymmetricHelper(left.left, right.right) && isSymmetricHelper(left.right, right.left);
  20.     }
  21.     //都为 null，返回 true
  22.     return true;
  23. }

解法二 DFS 栈

解法一其实就是类似于 DFS 的先序遍历。不同之处是对于 left 子树是正常的先序遍历 根节点 -> 左子树 -> 右子树 的顺序，对于 right 子树的话是 根节点 -> 右子树 -> 左子树 的顺序。

所以我们可以用栈，把递归改写为迭代的形式。

  1. public boolean isSymmetric(TreeNode root) { 
  2.     if (root == null) {
  3.         return true;
  4.     }
  5.     Stack<TreeNode> stackLeft = new Stack<>();
  6.     Stack<TreeNode> stackRight = new Stack<>();
  7.     TreeNode curLeft = root.left;
  8.     TreeNode curRight = root.right;
  9.     while (curLeft != null || !stackLeft.isEmpty() || curRight!=null || !stackRight.isEmpty()) {
  10.         // 节点不为空一直压栈
  11.         while (curLeft != null) {
  12.             stackLeft.push(curLeft);
  13.             curLeft = curLeft.left; // 考虑左子树
  14.         }
  15.         while (curRight != null) {
  16.             stackRight.push(curRight);
  17.             curRight = curRight.right; // 考虑右子树
  18.         }
  19.         //长度不同就返回 false
  20.         if (stackLeft.size() != stackRight.size()) {
  21.             return false;
  22.         }
  23.         // 节点为空，就出栈
  24.         curLeft = stackLeft.pop();
  25.         curRight = stackRight.pop();
  27.         // 当前值判断
  28.         if (curLeft.val != curRight.val) {
  29.             return false;
  30.         }
  31.         // 考虑右子树
  32.         curLeft = curLeft.right;
  33.         curRight = curRight.left;
  34.     }
  35.     return true;
  36. }

当然我们也可以使用中序遍历或者后序遍历，是一样的道理。

解法三 BFS 队列

DFS 考虑完了，当然还有 BFS，一层一层的遍历两个树，然后判断对应的节点是否相等即可。

利用两个队列来保存下一次遍历的节点即可。

  1. public boolean isSymmetric6(TreeNode root) {
  2.     if (root == null) {
  3.         return true;
  4.     }
  5.     Queue<TreeNode> leftTree = new LinkedList<>();
  6.     Queue<TreeNode> rightTree = new LinkedList<>();
  7.     //两个树的根节点分别加入
  8.     leftTree.offer(root.left);
  9.     rightTree.offer(root.right);
  10.     while (!leftTree.isEmpty() && !rightTree.isEmpty()) {
  11.         TreeNode curLeft = leftTree.poll();
  12.         TreeNode curRight = rightTree.poll();
  13.         if (curLeft == null && curRight != null || curLeft != null && curRight == null) {
  14.             return false;
  15.         }
  16.         if (curLeft != null && curRight != null) {
  17.             if (curLeft.val != curRight.val) {
  18.                 return false;
  19.             }
  20.             //先加入左子树后加入右子树
  21.             leftTree.offer(curLeft.left);
  22.             leftTree.offer(curLeft.right);
  24.             //先加入右子树后加入左子树
  25.             rightTree.offer(curRight.right);
  26.             rightTree.offer(curRight.left);
  27.         }
  29.     }
  30.     if (!leftTree.isEmpty() || !rightTree.isEmpty()) {
  31.         return false;
  32.     }
  33.     return true;
  34. }

总

总体上来说和 100 题 是一样的，只不过这里的两棵树对应相等，是左对右，右对左。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情