28.对称的二叉树

个人尝试（错误❌）

刚开始是想着看能不能有个 栈 来装 同一层中 对称轴 左边的节点，然后出栈跟对称轴右节点从左到右作对比

随后，看了题解思路后，想着用两个 ArrayList 装 前序遍历 的节点和 对称前序遍历的节点，然后对比ArrayList中的元素

/**
 * 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 checkSymmetricTree(TreeNode root) {
        if (root == null) return true;

        Deque<TreeNode> stack = new ArrayDeque<>();
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();

        stack.add(root);
        while (!stack.isEmpty()) {
            TreeNode tmp = stack.removeLast();
            list1.add(tmp.val);
            if (tmp.val != -1) {
                //使用 -1 标记空指针
                //左右子树为空也得进栈
                if (tmp.right != null) stack.add(tmp.right);
                else stack.add(new TreeNode(-1));

                if (tmp.left != null) stack.add(tmp.left);
                else stack.add(new TreeNode(-1));
            }
        }

        stack.add(root);
        while (!stack.isEmpty()) {
            TreeNode tmp = stack.removeLast();
            list2.add(tmp.val);
            //怎样才能让空指针进栈呢？
            if (tmp.val != -1) {
                //使用 -1 标记空指针
                //左右子树为空也得进栈
                if (tmp.left != null) stack.add(tmp.left);
                else stack.add(new TreeNode(-1));

                if (tmp.right != null) stack.add(tmp.right);
                else stack.add(new TreeNode(-1));
            }
        }

        for (int i = 0; i < list1.size(); i++) {
            if (list1.get(i) != list2.get(i)) return false;
        }
        return true;
    }
}

但是，空节点不知道怎么放进 ArrayDeque（前序遍历，迭代遍历中的栈） 中...

并且 还要区分 什么时候的空节点要进栈（同一层中有一个节点不为空），什么时候不用（空节点的子节点）

测试了下没有通过，遇到以下例子出错了

[3,67,67,18,null,null,18,-1,-64,-64,-1,null,61,-20,null,null,-20,null,61]

优秀题解

class Solution {
    public boolean checkSymmetricTree(TreeNode root) {
        return root == null || recur(root.left, root.right);
    }
    boolean recur(TreeNode L, TreeNode R) {
        if(L == null && R == null) return true;
        if(L == null || R == null || L.val != R.val) return false;
        return recur(L.left, R.right) && recur(L.right, R.left);
    }
}

作者：Krahets
链接：https://leetcode.cn/problems/dui-cheng-de-er-cha-shu-lcof/solutions/131626/mian-shi-ti-28-dui-cheng-de-er-cha-shu-di-gui-qing/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

看了优秀题解后，没想到直接递归遍历了，哪里还需要List存储节点再对比...

左节点 compare 右节点

两者为空？

两者其中之一为空？两者.val不行等？

划分问题：（左节点.左子树 compare 右节点.右子树） && （左节点.右子树 compare 右节点.左子树）