面向测试用例编程

自己写的： 中序遍历将数据加入到数组，判断是否为回文对称，但是，这个代码有bug,无法通过特殊测试用例。 alt

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
import java.util.*;
public class Solution {
    ArrayList<Integer> array=new ArrayList<>();
    boolean isSymmetrical(TreeNode pRoot) {
        int n=0;
        TreeNode temp=pRoot;
        inOder(pRoot);
  
        if(array.size()%2==0 && pRoot!=null ){
            return false;
        }
   
        for(int i=0;i<array.size();i++){
            if(array.get(i)!=array.get(array.size()-i-1)){
                return false;
            }
        }
        
        return true;
        
    }
    public void inOder(TreeNode node){
        if(node!=null){
            inOder(node.left);
            array.add(node.val);
            inOder(node.right);
        }
        
    }
}

还得是看看官方思路：

思路

前序遍历的时候我们采用的是“根左右”的遍历次序，如果这棵二叉树是对称的，即相应的左右节点交换位置完全没有问题，那我们是不是可以尝试“根右左”遍历，按照轴对称图像的性质，这两种次序的遍历结果应该是一样的。

不同的方式遍历两次，将结果拿出来比较看起来是一种可行的方法，但也仅仅可行，太过于麻烦。我们不如在遍历的过程就结果比较了。而遍历方式依据前序递归可以使用递归：

  1. 终止条件： 当进入子问题的两个节点都为空，说明都到了叶子节点，且是同步的，因此结束本次子问题，返回true；当进入子问题的两个节点只有一个为空，或是元素值不相等，说明这里的对称不匹配，同样结束本次子问题，返回false。
  2. 返回值： 每一级将子问题是否匹配的结果往上传递。
  3. 本级任务： 每个子问题，需要按照上述思路，“根左右”走左边的时候“根右左”走右边，“根左右”走右边的时候“根右左”走左边，一起进入子问题，需要两边都是匹配才能对称。

具体做法

  • step 1：两种方向的前序遍历，同步过程中的当前两个节点，同为空，属于对称的范畴。
  • step 2：当前两个节点只有一个为空或者节点值不相等，已经不是对称的二叉树了。
  • step 3：第一个节点的左子树与第二个节点的右子树同步递归对比，第一个节点的右子树与第二个节点的左子树同步递归比较 alt
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
import java.util.*;
public class Solution {
    ArrayList<Integer> array=new ArrayList<>();
    boolean isSymmetrical(TreeNode pRoot) {

        
        return inOder(pRoot,pRoot);
        
    }
    public boolean inOder(TreeNode node1,TreeNode node2){
        //当节点同时到达叶子结点
        if(node1==null && node2==null ){
            return true;
        }
        //有一个为空 或者值不相等  返回返回false
        if(node1==null || node2 ==null || node1.val!=node2.val){
            return false;
        }
        //对称进行前序遍历
     return inOder(node1.left,node2.right) && inOder(node1.right,node2.left);
        
    }
}