剑指Offer-对称的二叉树

男娘i 2022-04-24 13:46 170阅读 0赞

## 题目描述 ##

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

解题思路—**中序遍历**：使用**中序遍历同时搜索左右两棵子树**，在**遍历的过程中比对左右两棵子树的val**，若不相同或有单独的空树，返回false；反之，继续遍历。  
★解题思路—**递归**：上一种方法虽然也使用了递归，但是递归结构写的不好，代码冗余，直接将左右结点对比的结果return，代码会更加简洁。**推荐此种写法！**  
解题思路—**DFS**：**使用堆栈来实现树的深度优先遍历**，将左右结点**成对的压入堆栈**，出栈的时候也要**成对出栈**，若val不相同或是有单独的空树，返回false；否则，继续成对的压入左右结点。  
解题思路—**BFS**：**使用队列来实现树的广度优先遍历**，代码与DFS十分相似，只不过结点先进先出，同样要注意**入队以及出队**的时候，**左右结点要成对**。

## Java解题—中序遍历 ##

/*
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    */
    public class Solution {
        public int isSym = 0;
        boolean isSymmetrical(TreeNode pRoot)
        {
            if(pRoot==null)
                return true;
            TreeNode left = pRoot.left;
            TreeNode right = pRoot.right;
            mid(left, right);
            return isSym==0?true:false;
        }
        
        public void mid(TreeNode nodeleft, TreeNode noderight){
            if(isSym!=-1){
                if(nodeleft!=null && noderight!=null){
                    mid(nodeleft.left, noderight.right);
                    if(nodeleft.val!=noderight.val){
                        isSym = -1;
                        return;
                    }
                    mid(nodeleft.right, noderight.left);
                }else if((nodeleft==null && noderight!=null) || (nodeleft!=null && noderight==null)){
                    isSym = -1;
                    return;
                }
            }
        }
    }

## Java解题—递归 ##

public class Solution {
        boolean isSymmetrical(TreeNode pRoot)
        {
            if(pRoot==null)
                return true;
            return comValue(pRoot.left, pRoot.right);
        }
        
        public boolean comValue(TreeNode nodeleft, TreeNode noderight){
            if(nodeleft==null) return noderight==null;
            if(noderight==null) return false;
            if(nodeleft.val==noderight.val)
                return comValue(nodeleft.left, noderight.right) && comValue(noderight.left, nodeleft.right);
            return false;
        }
    }

## 解题思路—DFS ##

import java.util.Stack;
    public class Solution {
        boolean isSymmetrical(TreeNode pRoot)
        {
            if(pRoot==null)
                return true;
            Stack<TreeNode> stack = new Stack<>();
            stack.push(pRoot.left);
            stack.push(pRoot.right);
            while(!stack.isEmpty()){
                TreeNode right = stack.pop();
                TreeNode left = stack.pop();
                if (right==null && left==null)
                    continue;
                if(right==null || left==null)
                    return false;
                if(right.val!=left.val)
                    return false;
                
                stack.push(right.left);
                stack.push(left.right);
                stack.push(right.right);
                stack.push(left.left);
            }
            return true;
        }
    }

## 解题思路—BFS ##

import java.util.Queue;
    import java.util.LinkedList;
    public class Solution {
        boolean isSymmetrical(TreeNode pRoot)
        {
            if(pRoot==null)
                return true;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(pRoot.left);
            queue.offer(pRoot.right);
            while(!queue.isEmpty()){
                TreeNode right = queue.poll();
                TreeNode left = queue.poll();
                if (right==null && left==null)
                    continue;
                if(right==null || left==null)
                    return false;
                if(right.val!=left.val)
                    return false;
    
                queue.offer(right.left);
                queue.offer(left.right);
                queue.offer(right.right);
                queue.offer(left.left);
            }
            return true;
        }
    }