判断二叉树是否是对称二叉树

约定不等于承诺〃 2022-05-24 07:43 248阅读 0赞

![这里写图片描述][70]

import java.util.*;
    class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    public class Solution { 
         //判断一棵二叉树是否是对称的
        boolean isSymmetrical(TreeNode pRoot)
        {
            if(pRoot==null)
               return true;
            return isSymme(pRoot.left,pRoot.right);
    
        }
        //递归实现二叉树是否对称的
        public boolean isSymme(TreeNode left,TreeNode right){
                if(left==null) return right==null; 
                if(right==null) return false;
                if(left.val!=right.val) return false;
                return isSymme(left.left,right.right)&&isSymme(left.right,right.left);
    
        }
    
        //*****************************************************
    
        //方法二:对特殊情况不满足,不满足一般性
        boolean isSymmetrical2(TreeNode pRoot)
        {
             if(pRoot==null)
               return true;
             boolean isSymmetry=true;
             LinkedList<Integer>list1=new LinkedList<>();
             LinkedList<Integer>list2=new LinkedList<>();
             inSearch(pRoot,list1);
             inSearch2(pRoot,list2);
             for(int i=0;i!=list1.size();i++){
    
                  if(list1.get(i)!=list2.get(i))
                  {
    
                       isSymmetry=false;
                       break;
                  }
    
             }
             return isSymmetry;
        }
    
    
    
        //二叉树的中序遍历
        public void inSearch(TreeNode root,LinkedList<Integer>list){
    
             if(root!=null)
             {
                  inSearch(root.left,list);
                  list.add(root.val);
                  inSearch(root.right,list);
             }
        }
        //变形的二叉树的中序遍历
        public void inSearch2(TreeNode root,LinkedList<Integer>list){
    
             if(root!=null)
             {
                  inSearch2(root.right,list);
                  list.add(root.val);
                  inSearch2(root.left,list);
             }
        }
        //求一棵二叉树的镜像二叉树
        public TreeNode GetSymmetrical(TreeNode pRoot){
             if(pRoot.left==null&&pRoot.right==null)
                   return null;
              //交换左右子树
              TreeNode tmp=pRoot.left;
              pRoot.left=pRoot.right;
              pRoot.right=tmp;
              GetSymmetrical(pRoot.left);
              GetSymmetrical(pRoot.right);
    
              return pRoot;
        }
        public static void main(String[]args){
           // System.out.println("Hello");
            TreeNode root=new TreeNode(1);
            root.left=new TreeNode(2);
            root.right=new TreeNode(5);
            Solution s=new Solution();
            // LinkedList<Integer>list1=new LinkedList<>();
            // s.inSearch2(root,list1);
            System.out.println(s.isSymmetrical(root));
    
    
        }
    }

[70]: /images/20220524/d860e414c0e34318a0cad63b707dba21.png