1 题目描述
1.1 英文描述
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
Example 1:
Input: root = [1,2,2,3,4,4,3]
Output: true
Example 2:
Input: root = [1,2,2,null,3,null,3]
Output: false
1.2 中文描述
给你一个二叉树,你要判断它是否沿中轴线对称。
比如说,给你的二叉树是:
这棵二叉树是沿中轴线对称的,因此要返回 true。如果我去掉两个 4:
就不对称了,这时就要返回 false。
2 前置条件
2.1 树的结构
public static class TreeNode{
private int value;
private TreeNode left;
private TreeNode right;
public TreeNode(){
}
public TreeNode(int value, TreeNode left, TreeNode right) {
this.value = value;
this.left = left;
this.right = right;
}
}
3 解法
3.1 解法1 - 递归
使用递归解决
/**
* 方式1:递归
*/
public static boolean isSymmetricTree(TreeNode root){
return root != null && helper(root.left,root.right);
}
public static boolean helper(TreeNode left,TreeNode right){
if(left == null && right == null){
return true;
}
if((left != null && right == null) || (left == null && right != null)){
return false;
}
if(left.value != right.value){
return false;
}
return helper(left.left,right.right) && helper(left.right,right.left);
}
3.2 解法2 - 栈
使用栈辅助解决
/**
* 方式2:栈
*/
public static boolean isSymmetricTree2(TreeNode root){
if(root == null){
return true;
}
Stack<TreeNode> stack = new Stack<>();
if(root.left != null){
if(root.right != null){
stack.push(root.left);
stack.push(root.right);
}else {
return false;
}
}else if(root.right != null){
return false;
}
while (!stack.isEmpty()){
if(stack.size() % 2 != 0){
return false;
}
TreeNode left = stack.pop();
TreeNode right = stack.pop();
if(left.value != right.value){
return false;
}
if(left.left != null){
if(right.right != null){
stack.push(left.left);
stack.push(right.right);
}else {
return false;
}
}else if(right.right != null){
return false;
}
if(left.right != null){
if(right.left != null){
stack.push(left.right);
stack.push(right.left);
}else {
return false;
}
}else if(right.left != null){
return false;
}
}
return true;
}