对称二叉树（Leetcode 101）

题目

101. 对称二叉树 

思路

使用层序遍历，遍历当前层的节点时，如该节点的左（右）孩子为空，在list中添加null，否则加入左（右）孩子的值。每遍历完一层则对当前list进行判断，这里判断我用了一个很笨的方法，前面记录下一层节点值时就设置了两个list，其中一个用来翻转，然后判断这两个list是否相等来判断数是否为对称树。

去看了解析，有两种方法：递归法、使用双端队列进行迭代。

代码

public boolean isSymmetric(TreeNode root) {
//        迭代写法：使用双端队列if(root == null){return true;}Deque<TreeNode> deque = new LinkedList<TreeNode>();deque.offerFirst(root.left);deque.offerLast(root.right);while (!deque.isEmpty()){TreeNode temp_left = deque.pollFirst();TreeNode temp_right = deque.pollLast();if(temp_left == null && temp_right == null){continue;}if(temp_left == null || temp_right == null || temp_left.val != temp_right.val){return false;}deque.offerFirst(temp_left.right);deque.offerFirst(temp_left.left);deque.offerLast(temp_right.left);deque.offerLast(temp_right.right);}return true;}public boolean isSymmetric_2(TreeNode root) {
//        递归写法：分解为判断每个子树是否对称if(root == null){return true;}return comp(root.left, root.right);}public boolean comp(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;}
//        当左右子树都不为空且值相等时，对其左右子树继续进行判断return comp(left.left, right.right)&&comp(left.right, right.left);}public boolean isSymmetric_1(TreeNode root) {
//        判断二叉树是否为轴对称二叉树
//        直接拿层序遍历的结果，看逆转后是否还为原数组来进行判断if(root == null){return false;}Queue<TreeNode> queue = new ArrayDeque<TreeNode>();queue.add(root);while (!queue.isEmpty()){int len = queue.size();List<Integer> temp_list = new ArrayList<Integer>();List<Integer> temp_re = new ArrayList<Integer>();while (len > 0){TreeNode temp = queue.poll();if(temp.left == null){temp_list.add(null);temp_re.add(null);}if(temp.left != null){queue.add(temp.left);temp_list.add(temp.left.val);temp_re.add(temp.left.val);}if(temp.right == null){temp_list.add(null);temp_re.add(null);}if(temp.right != null){queue.add(temp.right);temp_list.add(temp.right.val);temp_re.add(temp.right.val);}len--;}Collections.reverse(temp_list);if(!temp_list.equals(temp_re)){return false;}}return true;}