Leetcode原题
思路
依据题意，要求判断二叉树是否对称。我们可以观察发现，左子树的左节点和右子树的右节点相等。左子树的右节点和右子树的左节点相等，即可。这中间，若左右子树的值不相等，或为空，那必然不是对称二叉树。
方法一 递归
class Solution { public boolean isSymmetric(TreeNode root) { if(root ==null){ return true; } return deepCheck(root.left, root.right); } public boolean deepCheck(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 deepCheck(left.left, right.right) && deepCheck(left.right, right.left); } }
方法二迭代
首先我们引入一个队列，这是把递归程序改写成迭代程序的常用方法。初始化时我们把根节点入队两次。每次提取两个结点并比较它们的值（队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像），然后将两个结点的左右子结点按相反的顺序插入队列中。当队列为空时，或者我们检测到树不对称（即从队列中取出两个不相等的连续结点）时，该算法结束。
class Solution { public boolean isSymmetric(TreeNode root) { return check(root, root); } public boolean check(TreeNode u, TreeNode v) { Queue<TreeNode> q = new LinkedList<TreeNode>(); q.offer(u); q.offer(v); while (!q.isEmpty()) { u = q.poll(); v = q.poll(); if (u == null && v == null) { continue; } if ((u == null || v == null) || (u.val != v.val)) { return false; } q.offer(u.left); q.offer(v.right); q.offer(u.right); q.offer(v.left); } return true; } }
有兴趣的老爷，还可以关注我的公众号【一起收破烂】，回复【006】获取 最新java面试资料以及简历模型120套哦~
