判断二叉树是否对称

雨点打透心脏的1/2处 2022-08-04 09:19 142阅读 0赞

题意：判断一棵二叉树是否对称，即该二叉树同它的镜像是否一样

思路：

1、层次遍历二叉树；

2、空节点用 -1 代替。

/*
    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 {
        // 层次遍历，按层比较，为空用特殊字符代替
        private List<List<Integer>> resList = new ArrayList<List<Integer>>() ;
        boolean isSymmetrical(TreeNode pRoot)
        {
            levelTraversal(0, pRoot) ;
            for(int i = 0; i < resList.size(); i ++) {
                List<Integer> r = resList.get(i) ;
                int j = 0, k = r.size() - 1;
                while(j < k) {
                    if(r.get(j) != r.get(k)) {
                        return false ;
                    }
                    j ++ ;
                    k -- ;
                }
            }
            return true ;
        }
         
        public int levelTraversal(int dep, TreeNode root) {
    		if(root == null) {
    			return 0;
    		}
    		if(resList.size() > dep) {
    			resList.get(dep).add(root.val) ;
    		} else {
    			List<Integer> r = new ArrayList<Integer>() ;
    			r.add(root.val) ;
    			resList.add(r) ;
    		}
    		
    		int flagL = levelTraversal(dep+1, root.left);
    		if(flagL == 0) {
    			if(resList.size() > (dep + 1)) {
    				resList.get(dep + 1).add(-1) ;
    			} else {
    				List<Integer> r = new ArrayList<Integer>() ;
    				r.add(-1) ;
    				resList.add(r) ;
    			}
    		}
    		
    		int flagR = levelTraversal(dep+1, root.right) ;
    		if(flagR == 0) {
    			if(resList.size() > (dep + 1)) {
    				resList.get(dep + 1).add(-1) ;
    			} else {
    				List<Integer> r = new ArrayList<Integer>() ;
    				r.add(-1) ;
    				resList.add(r) ;
    			}
    		}
    		return 1 ;
    	}
    }