判断相同的二叉树

解题过程

1.基本思路：

由于本人是菜鸡出炉，所以我用的是二叉树中最基础的前序、中序和后序遍历，首先我们明白，前序+中序或者中序+后序可以确定唯一一个二叉树，但是先序+后序不行，所以我采用的是先序加中序的方法. 不过后序遍历的方法写成注释了。遍历我就不解释了。 对于遍历的结果，我采用List接口的一个实现类--ArrayList来存储，用add(Object obj)方法存数据，然后在比较时用get(int index)方法来获取。这里注意我将root是否为null的判断结果也存储进去了，这样就可以解决一个问题：一个测试用例是 [1,1],[1,#,1]如果按照这样遍历来写，那么null他是不会进行添加的，也就是最后都是[1,1],[1,1]但是他们是两个不一样的树。 要判断是否相同，我先进行判断他们返回的ArrayList长度是否相同，如果不同，则返回false，如果相同，继续操作，就是将数据取出来一个一个比较，非常老实的想法

2.注意点和问题

一个问题我在上文写了：一个测试用例是 [1,1],[1,#,1]如果按照这样遍历来写，那么null他是不会进行添加的，也就是最后都是[1,1],[1,1]但是他们是两个不一样的树 还有一个非常严重的问题，我这个答案在牛客网可以通过，但是在LeetCode上面无法通过(LeetCode是第100题)，在LeetCode通过了59/60个例子，唯独最后一个例子没通过，我想了很久也没有解决这个问题，想用debug调试，发现要钱，所以我来牛客网想白嫖(不是)调试，然后就写下这个博客。希望有大佬能解决我这个疑惑

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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root1 TreeNode类 
     * @param root2 TreeNode类 
     * @return bool布尔型
     */
    public boolean isSameTree (TreeNode root1, TreeNode root2) {
        // write code here
        List listp1 = new ArrayList();
        List listq1 = new ArrayList();
        List listp2 = new ArrayList();
        List listq2 = new ArrayList();
        // List listp3 = new ArrayList();
        // List listq3 = new ArrayList();
        preOrderTraversal(listp1, root1);
        preOrderTraversal(listq1, root2);
        inOrderTraversal(listp2, root1);
        inOrderTraversal(listq2, root2);
        //    postOrderTraversal(listp3,p);
        //    postOrderTraversal(listq3,q);
        if (listp1.size() != listq1.size()) {
            return false;
        }

        for (int i = 0; i < listp1.size(); i++) {
            if (listp1.get(i) != listq1.get(i)) {
                return false;
            }
        }
        for (int i = 0; i < listp2.size(); i++) {
            if (listp2.get(i) != listq2.get(i)) {
                return false;
            }
        }
        
         //    for(int i=0;i<listp3.size();i++){
        //        if(listp3.get(i)!=listq3.get(i)){
        //            return false;
        //        }
        //    }
       
        return true;


    }

    public void preOrderTraversal(List list, TreeNode root) {
        if (root == null) {
            list.add(null);
            return;
        }
        list.add(root.val);
        preOrderTraversal(list, root.left);
        preOrderTraversal(list, root.right);
    }

    public void inOrderTraversal(List list, TreeNode root) {
        if (root == null) {
            list.add(null);
            return;
        }
        inOrderTraversal(list, root.left);
        list.add(root.val);
        inOrderTraversal(list, root.right);
    }
    // public void postOrderTraversal(List list,TreeNode root){
    //     if(root==null){
    //         list.add(null);
    //         return;
    //     }
    //     postOrderTraversal(list,root.left);
    //     postOrderTraversal(list,root.right);
    //     list.add(root.val);
    // }
   
    
    
}