（二叉树）Java 求解对称二叉树

妖狐艹你老母 2023-01-20 08:04 51阅读 0赞

### 文章目录 ###

*   *  一、题目
     *  二、题目分析
     *  三、递归法
     *  四、迭代法
     *  五、总结

## 一、题目 ##

给定一个二叉树，检查它是否是镜像对称的

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70]

## 二、题目分析 ##

题目要求比较的是二叉树是否对称，其实比较的是树的左右子树，所以递归遍历的过程中，也是要同时遍历两棵树

比较的两个子树的里侧和外侧的元素是否相等  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70 1]  
因为要遍历两棵树而且要比较内侧和外侧节点，所以准确的来说是一个树的遍历顺序是左右中，一个树的遍历顺序是右左中

## 三、递归法 ##

（1）确定递归参数及返回值

> 返回值就是判断的结果true或者false  
> 递归参数需要传递左子树和右子树

boolean isCompare(TreeNode left,TreeNode right);

（2）确定递归终止条件

> 左为空，右不为空，不对称，return false  
> 左不为空，右为空，不对称 return false  
> 左右都为空，对称，return true  
> 左右都不为空，比较节点数值，不相同就 return false

（3）确定单层递归的逻辑

> 比较的是左子树的左孩子和右子树的右孩子  
> 左子树的右孩子和右子树的左孩子  
> 也就是内测内测进行比较，外侧外侧进行比较

class Solution { 
        public boolean isSymmetric(TreeNode root) { 
            if (root == null) { 
                return true;
            }
            //比较左右子树
            return isCompare(root.left, root.right);
        }
    
        public boolean isCompare(TreeNode left, TreeNode right) { 
            //排除空节点的情况
            if (left == null && right == null) { 
                return true;
            }
            if (left == null && right != null) { 
                return false;
            }
            if (left != null && right == null) { 
                return false;
            }
            //排除左右节点都不为空的情况
            if (left.val != right.val) { 
                return false;
            }
            //当前节点值相同
            //外侧：递归比较左子树的左孩子和右子树的右孩子
            //内测：递归比较左子树的右孩子和右子树的左孩子
            return isCompare(left.left, right.right) && isCompare(left.right, right.left);
        }
    }

## 四、迭代法 ##

借助队列判断根节点的左子树和右子树的内测和外侧是否相等

class Solution { 
        public boolean isSymmetric(TreeNode root) { 
            if (root == null) { 
                return true;
            }
            Deque<TreeNode> deque = new LinkedList<>();
            deque.add(root.left);
            deque.add(root.right);
            //记录左右子树要比较的节点
            TreeNode leftNode, rightNode;
            while (!deque.isEmpty()) { 
                leftNode = deque.poll();
                rightNode = deque.poll();
                //左右节点均为空
                if (leftNode == null && rightNode == null) { 
                    continue;
                }
                //左右节点有一个为空，或者两者值不等
                if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) { 
                    return false;
                }
                //先加入外侧节点进行比较
                deque.add(leftNode.left);
                deque.add(rightNode.right);
                //再加入内测节点进行比较
                deque.add(leftNode.right);
                deque.add(rightNode.left);
            }
            return true;
        }
    }

## 五、总结 ##

分析题目，注意递归和迭代的写法

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70]: /images/20221021/c40dad3c2896483c9f785aaabbb83596.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70 1]: /images/20221021/59ca8ac033b7409097ddd31f71755921.png