题解 | #对称的二叉树#

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return bool布尔型
     */
    private void preorderTravel(TreeNode vroot, ArrayList temp){
        if(vroot.left!=null){
            preorderTravel(vroot.left, temp);
        }
        temp.add(null);
        temp.add(vroot.val);
        if(vroot.right!=null){
            preorderTravel(vroot.right, temp);
        }
        temp.add(null);
    }

    private void symetricPreoder(TreeNode vroot, ArrayList temp){
        if(vroot.right!=null){
            symetricPreoder(vroot.right, temp);
        }
        temp.add(null);
        temp.add(vroot.val);
        if(vroot.left!=null){
            symetricPreoder(vroot.left, temp);
        }
        temp.add(null);
    }
    
    public boolean isSymmetrical (TreeNode pRoot) {
        // write code here
        if(pRoot==null) return true;


        ArrayList<Integer> temp1 = new ArrayList<Integer>();
        ArrayList<Integer> temp2 = new ArrayList<Integer>();

        preorderTravel(pRoot, temp1);
        symetricPreoder(pRoot, temp2);

        // for(int i=0;i<temp1.size();i++){
        //     System.out.println(temp1.get(i));
        // }

        // for(int i=0;i<temp2.size();i++){
        //     System.out.println(temp2.get(i));
        // }
        

        return temp1.equals(temp2);
        
    }
}

首先大体的思想是用一个中序遍历和一个镜像的中序遍历来分别构造两个ArrayList对象，然后判断这两个ArrayList是否相同

但是，关键在于，如果出现{1，2，3，3，#，2，#}这样的情况时，会失效。

办法就是在遍历中间加入一些null，使得它们可以区分开来，这一招自己想的，但是有点神奇