代码随想录二叉树——对称二叉树

题目

给定一个二叉树，检查它是否是镜像对称的。

思路

判断二叉树是否对称，比较的是根节点的左子树和右子树是不是相互翻转的（即比较两个子树的里侧和外侧的元素是否相等）

1. 递归法

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;
        }
        if(left != null && right == null){
            return false;
        }
        if(left == null && right == null){
            return true;
        }
        if(left.val != right.val){
            return false;
        }
        //比较外侧，即将左子树的左孩子和右子树的右孩子进行对比
        boolean compareOutside = compare(left.left,right.right);
        //比较内侧，即将左子树的右孩子和右子树的左孩子进行对比
        boolean compareInside = compare(left.right,right.left);
        return compareOutside && compareInside;
    }   
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

2. 迭代法

使用队列不断比较是否相同

//使用普通队列，
class Solution {
	public boolean isSymmetric(TreeNode root){
		Queue<TreeNode> queue = new LinkedList<>();//创建队列
		//将根节点左右子树入队
		queue.offer(root.left);
		queue.offer(root.right);
		while(!queue.isEmpty()){//如果队列非空则出队列
			TreeNode leftNode = queue.poll();//因为先进先出，先入的左孩子，所以先出的也是左孩子
			TreeNode rightNode = queue.poll();
			//定义判断对称的逻辑
			if(leftNode == null && rightNode == null){
				continue;
			}
			if(leftNode == null && rightNode != null){
				return false;
			}
			if(leftNode != null && rightNode == null){
				return false;
			}
			if(leftNode.val != rightNode.val){
				return false;
			}
			//将左子树的左孩子和右子树的右孩子进行对比，外侧对比
			queue.offer(leftNode.left);
			queue.offer(rightNode.right);
			//再将左子树的右孩子和右子树的右孩子进行对比，内侧对比
			queue.offer(leftNode.right);
			queue.offer(rightNode.left);
		}
		return true;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33