1月4日代码随想录对称二叉树

101.对称二叉树

101. 对称二叉树 - 力扣（LeetCode）

给你一个二叉树的根节点?root?， 检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

提示：

• 树中节点数目在范围?[1, 1000]?内
• -100 <= Node.val <= 100

进阶：你可以运用递归和迭代两种方法解决这个问题吗？

思路

递归法

这道题的重点就是检查根节点的左子树是否与右子树的反转相同，开始想的是前序遍历和后序遍历的反转比较，但是好像不太对而且可能没有唯一性，所以我们使用递归法比较直观。

那么我们应该同时对左右子树的内侧或者外侧进行递归，结束条件有：1、左右节点均为空视为对称2、左右节点有一为空视为不对称3、左右节点值不相同视为不对称。

在判断完结束条件之后正式进入递归过程，在这个时候，假设左右节点都有左右子节点，那么根据翻转，我们需要对左左&右右，左右&右左继续进行遍历，返回两次遍历返回值的交。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null){
            return true;
        }
        return dfs(root.left,root.right);
    }
    public boolean dfs(TreeNode left, TreeNode right){
        if(left==null&&right==null){
            return true;
        }
        if(left==null||right==null){
            return false;
        }
        if(left.val!=right.val){
            return false;
        }
        return dfs(left.left,right.right)&&dfs(left.right,right.left);
    }
}

迭代法

我们也可以使用队列来完成这道题，怎样去判断是否对称呢？我们可以在加入根节点的左右子节点后，每次添加队列都是将队首的两个节点的对称的子节点双双加入队列，出队也是两个两个出，在同时也加入判空等操作。

class Solution {
	public boolean isSymmetric(TreeNode root) {
		if(root==null || (root.left==null && root.right==null)) {
			return true;
		}
		//用队列保存节点
		LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
		//将根节点的左右孩子放到队列中
		queue.add(root.left);
		queue.add(root.right);
		while(queue.size()>0) {
			//从队列中取出两个节点，再比较这两个节点
			TreeNode left = queue.removeFirst();
			TreeNode right = queue.removeFirst();
			//如果两个节点都为空就继续循环，两者有一个为空就返回false
			if(left==null && right==null) {
				continue;
			}
			if(left==null || right==null) {
				return false;
			}
			if(left.val!=right.val) {
				return false;
			}
			//将左节点的左孩子， 右节点的右孩子放入队列
			queue.add(left.left);
			queue.add(right.right);
			//将左节点的右孩子，右节点的左孩子放入队列
			queue.add(left.right);
			queue.add(right.left);
		}
		
		return true;
	}
}

总结

迭代和递归两种方法，深搜广搜两种方法，写起来简单，想起来还需要有一定的理解熟练度。