https://leetcode-cn.com/problems/symmetric-tree/
题目
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [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,2,3,4,4,3]
前序遍历：1 2 3 4 2 4 3
中序遍历：3 2 4 1 4 2 3
后序遍历：3 4 2 4 3 2 1
先中序遍历，再对所得列表进行遍历，双指针
代码
class Solution {
public boolean isSymmetric(TreeNode root) {
//先遍历
List<Integer> res = new ArrayList<Integer>();
preorder(root,res);
for(int i=0,j=res.size()-1;i<j;i++,j--){
if(res.get(i)!=res.get(j)){
return false;
}
}
return true;
}
//中序遍历
public void preorder(TreeNode root,List<Integer> res){
if(root == null){
return;
}
preorder(root.left,res);
res.add(root.val);
preorder(root.right,res);
}
}
[1,2,2,2,null,2]
中序遍历为：2 2 null 1 2 2 null 不是对称，却返回true
因为null没有遍历进去，中序遍历是2 2 1 2 2
194/197通过用例
其他优解
思路
递归
root节点的左右指针l、r.
结束条件：左右都为空、左右有一个为空、左右值不等
递归逻辑：左孩子遍历左子树，右孩子则遍历右子树；左孩子遍历右子树，右孩子则遍历左子树。
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null){
return true;
}
return dfs(root.left,root.right);
}
//递归函数
public boolean dfs(TreeNode l,TreeNode r){
//中止条件 两节点为空、或者有一方为空、或者节点值不相等
if(l==null && r==null){
return true;
}
if(l==null || r==null){
return false;
}
return l.val==r.val && dfs(l.left,r.right) && dfs(l.right,r.left);
}
}