题解 | #对称的二叉树#

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布尔型
     */
    public boolean isSymmetrical (TreeNode pRoot) {
        // write code here

        // 思路 获取层序遍历，然后每层数组是对称的则代表整个数对称
        if(pRoot == null) {
            return true;
        }
        List<List<Integer>> list = new ArrayList();
        levelIterator(pRoot,1,list);
        System.out.println(list);

        for(int i=0;i<list.size();i++) {
            List<Integer> levelList = list.get(i);
            // 对某层数组进行反转
            List<Integer> reverseList = new ArrayList<Integer>();
            reverseList.addAll(levelList);
            Collections.reverse(reverseList);
            // 原数组和反转后的数组通过toString是否相同判断该层是否对称
            if(!levelList.toString().equals(reverseList.toString())) {
                return false;
            }
        }
        
        return true;
    }

    // 层序遍历 返回[[第一层列表],[第二层列表],...]，需要注意的是：如果左右子节点中若仅其中一个为null，需要再创建一个临时节点，节点值为-1，这么做是为了后面对某一层是否对称判断用的。
    public void levelIterator(TreeNode node,int level,List<List<Integer>> list) {
        // level 从1开始
        List<Integer> levelList = new ArrayList<Integer>();
        if(list.size() < level) {
            list.add(levelList);
        } else {
            levelList = list.get(level - 1);
        }
        levelList.add(node.val);
        if(node.left != null && node.right != null) {
            levelIterator(node.left,level + 1,list);
            levelIterator(node.right,level + 1,list);
        }
        if(node.left != null && node.right == null) {
            levelIterator(node.left,level + 1,list);
            node.right = new TreeNode(-1);
            levelIterator(node.right,level + 1,list);
        }
        if(node.left == null && node.right != null) {
            node.left = new TreeNode(-1);
            levelIterator(node.left,level + 1,list);
            
            levelIterator(node.right,level + 1,list);
        }

        if(node.left == null && node.right == null) {
            
        }
    }







}