【刷题】Leetcode 101. Symmetric Tree

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

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

But the following [1,2,2,null,3,null,3] is not:

1 / \ 2 2 \ \ 3 3

最近刷的还是老题，想提高下速度，结果每天也是各种事耽误着。恍恍惚惚莺莺燕燕碌碌无为就是了。

这道题想到的是层遍历每一行，再判断是否是回文。当然也可以递归来做。记得以前刷的时候是递归做的，但是现在用它练下BFS。

Runtime: 1 ms, faster than 48.79% of Java online submissions for Symmetric Tree.

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isSymmetric(TreeNode root) { Queue<TreeNode> q = new LinkedList<TreeNode>(); q.offer(root); while(!q.isEmpty()){ int size = q.size(); ArrayList<Integer> list = new ArrayList<Integer>(); for(int i = 0; i < size; i++){ TreeNode node = q.poll(); if(node == null) list.add(-1); else{ list.add(node.val); q.add(node.left); q.add(node.right); } } if(!isPalindrome(list)) return false; } return true; } public boolean isPalindrome(ArrayList<Integer> list){ int l = 0; int r = list.size() - 1; while(l <= r){ if(list.get(l) != list.get(r)) return false; l++; r--; } return true; } }

总结：

在这句话刚开始出错了，每一层回来得重新定义新的list, 脑子不太好使。ArrayList list = new ArrayList();为空的情况， list.add(-1);感觉这种方法挺笨，纯是晚上自己想的。

递归写法：

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isSymmetric(TreeNode root) { if(root == null) return true; return helper(root.left, root.right); } public boolean helper(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 helper(left.left, right.right) && helper(left.right, right.left); } }