Java详解剑指offer面试题27对称的二叉树

请实现一个函数&＃xff0c;用来判断一颗二叉树是不是对称的。注意&＃xff0c;如果一个二叉树同此二叉树的镜像是同样的&＃xff0c;定义其为对称的。


对称的二叉树&＃xff0c;结点数必然是奇数&＃xff0c;特别地定义空树也是对称的。当对称树的结点值不是完全相同时比较好处理&＃xff0c;但是当结点值全部一样时候可能会有些麻烦。我们要实现一个通用的算法&＃xff0c;使得对于这种特殊情况也能正确处理。

要保证树是对称的&＃xff0c;左子树最左边的结点要和右子树最右边的结点值相同…左子树的右子结点要和右子树的左子结点值相同&＃xff0c;即

root1.left &＃61;&＃61; root2.right;
root1.right &＃61;&＃61; root2.left;


这是关键&＃xff0c;理解了上面说的&＃xff0c;可以很轻松地写出下面的代码。

递归版本

先来看递归版本&＃xff0c;递归的实现一般比较简单、清晰。

package Chap4;import java.util.LinkedList;
import java.util.Queue;public class SymmetricalTree {public class TreeNode {int val &＃61; 0;TreeNode left &＃61; null;TreeNode right &＃61; null;public TreeNode(int val) {this.val &＃61; val;}}/*** 递归实现*/public boolean isSymmetricalRecur(TreeNode pRoot) {if (pRoot &＃61;&＃61; null) return true;return isSymmetrical(pRoot.left, pRoot.right);}private boolean isSymmetrical(TreeNode root1, TreeNode root2) {if (root1 &＃61;&＃61; null && root2 &＃61;&＃61; null) return true;if (root1 &＃61;&＃61; null || root2 &＃61;&＃61; null) return false;if (root1.val !&＃61; root2.val) return false;return isSymmetrical(root1.left, root2.right)&& isSymmetrical(root1.right, root2.left);}
}

如果遇到两棵子树都为空流返回true&＃xff0c;这句代码隐含了**“空树也是对称的”**这样的信息。否则&＃xff0c;只有一子树为空另一不为空&＃xff0c;显然不是对称的&＃xff1b;如果两个子树都不为空&＃xff0c;比较它俩根结点的值&＃xff0c;不相同肯定不是对称的。之后递归地对树的子树进行上述判断&＃xff0c;直到检查到叶子结点&＃xff0c;如果都满足就返回true。

非递归版本

思路和上面一样&＃xff0c;非递归实现需要用到两个队列。队列A专门存入左子树&＃xff0c;队列B专门存入右子树。

入列时&＃xff0c;将左子树的左子结点和右子树的右子结点分别存入队列A和队列B&＃xff0c;紧接着还要将左子树的右子结点和右子树的左子结点分别存入队列A和队列B。

出列时&＃xff0c;两个队列同时出列一个元素&＃xff0c;根据存入的顺序&＃xff0c;这两个出列元素就是左子树的左子结点和右子树的右子结点&＃xff0c;或者左子树的右子结点和右子树的左子结点。之后对这两个元素进行比较&＃xff0c;比较操作和上面递归版本的一样。

package Chap4;import java.util.LinkedList;
import java.util.Queue;public class SymmetricalTree {/*** 非递归&＃xff0c;队列实现(栈也可以实现)*/public boolean isSymmetrical(TreeNode pRoot) {if (pRoot &＃61;&＃61; null) return true;Queue<TreeNode> queueA &＃61; new LinkedList<>();Queue<TreeNode> queueB &＃61; new LinkedList<>();queueA.offer(pRoot.left);queueB.offer(pRoot.right);TreeNode left &＃61; null;TreeNode right &＃61; null;while (!queueA.isEmpty() && !queueB.isEmpty()) {left &＃61; queueA.poll();right &＃61; queueB.poll();// 两个都空跳过if (left &＃61;&＃61; null && right &＃61;&＃61; null) continue;// 只有一个空&＃xff0c;不对称if (left &＃61;&＃61; null || right &＃61;&＃61; null) return false;// 两个都不空&＃xff0c;比较值if (left.val !&＃61; right.val) return false;// 两两对称的加入// 左孩子的左孩子&＃xff0c;右孩子的右孩子queueA.offer(left.left);queueB.offer(right.right);// 左孩子的右孩子&＃xff0c;右孩子的左孩子queueA.offer(left.right);queueB.offer(right.left);}return true;}
}

本文参考文献&＃xff1a;
[1]github.com/haiyusun/data-structures