leetcode 101.对称二叉树

思路一：这里作者用了前序遍历的方法，并对前序遍历稍作了修改，对这个树的左右子树进行遍历并用集合进行了存储（即使是遍历到空结点也需要向里面添加null），然后比较两个集合中的元素是否一一对应。如出现一个不对应的地方，就直接返回false。遍历结束，还是没有出现不对应的地方，就说明这是一个轴对称的树。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isSymmetric(TreeNode root) {if(root==null)return false;List list1=new ArrayList();qianxu1(root.left,list1);List list2=new ArrayList();qianxu2(root.right,list2);if(list1.size()!=list2.size())return false;int len=Math.max(list1.size(),list2.size());for(int i=0;i<len;i++){if(list1.get(i)!=list2.get(i)){return false;}}return true;}public void qianxu1(TreeNode t,List list){if(t==null){list.add("null");return;}else{list.add(t.val);qianxu1(t.left,list);qianxu1(t.right,list);}}public void qianxu2(TreeNode t,List list){if(t==null){list.add("null");return;}list.add(t.val);qianxu2(t.right,list);qianxu2(t.left,list);}
}

思路二：可以递归同时进行，依次指向两节点其中的一个结点的左子树，和另一个结点的右子树，判断其某节点的左子树和另一个结点的右子树的元素是不是相同。一开始作者有这个思路，但是因为空指针异常，放弃了这个做法，是因为作者觉得根结点是特殊的，最多只有两个儿子，不需要颠倒左右子树；但即使这样也可以这样写，顶多就是重复而已，对于下面的结点就不一样了，有自己的左子树右子树。

当时在写这种思路的时候，提前去判断当前结点的左子树和右子树的元素是否相同，这样就会导致不知道当前结点的左子树或者右子树是否存在，也就会抛出指针异常的问题。给我的教训就是，有指针的地方，必须首先判断当前指针的有无，不要提前去判断下一次递归的指针的元素。然后再去递归下面可能存在的指针，在下一次递归中判断这个可能存在的指针到底是不是存在，也就是写在递归函数最前面判断指针是不是null的部分判断。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isSymmetric(TreeNode root) {if(root==null)return false;return bianli(root,root);}public boolean bianli(TreeNode t1,TreeNode t2){if(t1==null&&t2==null)return true;if(t1==null||t2==null)return false;if(t1.val==t2.val){return bianli(t1.left,t2.right)&&bianli(t1.right,t2.left); }elsereturn false;}
}