对称二叉树

ゝ一纸荒年。 2022-02-27 06:42 177阅读 0赞

题目描述

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

例如，二叉树 \[1,2,2,3,4,4,3\] 是对称的。

1
       / \
      2   2
     / \ / \
    3  4 4  3

但是下面这个 \[1,2,2,null,3,null,3\] 则不是镜像对称的:

1
       / \
      2   2
       \   \
       3    3

**说明:**

如果你可以运用递归和迭代两种方法解决这个问题，会很加分。

**解法**  
如果一个树的左子树与右子树镜像对称，那么这个树是对称的。  
因此，该问题可以转化为：两个树在什么情况下互为镜像？  
如果同时满足下面的条件，两个树互为镜像：

1.  它们的两个根结点具有相同的值
2.  每个树的右子树都与另一个树的左子树镜像对称

思路1：对称二叉树为左右子树：  
左树的左子节点 = 右树的右子节点  
左树的右子节点 = 右树的左子节点  
故使用广度优先遍历，  
左子树入队列顺序为（左子节点—>右子节点）  
左子树入队列顺序为（右子节点—>左子节点）  
然后判断每个节点值是否相同就完事儿了，代码如下

public boolean isSymmetric(TreeNode root) { 
            if(root == null || (root.left == null && root.right == null)) { 
            	return true;
            }
            //判断左右子树相等（因为判断的是所有当前节点的左子节点是否等于另一方的右子节点，故使用广度优先）
            LinkedList<TreeNode> lQueue = new LinkedList<TreeNode>();
            LinkedList<TreeNode> rQueue = new LinkedList<TreeNode>();
            TreeNode lNode = root.left;
            TreeNode rNode = root.right;
            if(lNode == null || rNode == null) { 
            	return false;
            }
            lQueue.offer(lNode);
            rQueue.offer(rNode);
            while(!lQueue.isEmpty() || !rQueue.isEmpty()) { 
            	lNode=lQueue.poll();
            	rNode=rQueue.poll();
            	if(lNode.val != rNode.val) { 
            		return false;
            	}
            	if((lNode.left!=null && rNode.right==null) || (lNode.left==null && rNode.right!=null)) { 
            		return false;
            	}else if (lNode.left!=null && rNode.right!=null) { 
    				lQueue.offer(lNode.left);
    				rQueue.offer(rNode.right);
    			}
            	
            	if((lNode.right!=null && rNode.left==null) || (lNode.right==null && rNode.left!=null)) { 
            		return false;
            	}else if (lNode.right!=null && rNode.left!=null) { 
    				lQueue.offer(lNode.right);
    				rQueue.offer(rNode.left);
    			}
            }
    		return true;
        }

思路2：**递归版**

public boolean isSymmetric(TreeNode root) { 
    		return isMirror(root, root);
    	}
    	
    	public boolean isMirror(TreeNode t1, TreeNode t2) { 
    		if(t1 == null && t2==null) { 
    			return true;
    		}
    		if(t1 == null || t2 == null) { 
    			return false;
    		}
    		return t1.val == t2.val && isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);
    	}

注：TreeNode代码如下

class TreeNode { 
    	int val;
    	public TreeNode(int val) { 
    		this.val = val;
    	}
    	TreeNode left;
    	TreeNode right;
    	
    }