剑指 Offer 28. 对称的二叉树

我就是我 2022-09-10 04:24 171阅读 0赞

> 请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
> 
> 例如，二叉树 \[1,2,2,3,4,4,3\] 是对称的。
> 
> 1  
> / \\  
> 2 2  
> / \\ / \\  
> 3 4 4 3  
> 但是下面这个 \[1,2,2,null,3,null,3\] 则不是镜像对称的:
> 
> 1  
> / \\  
> 2 2  
> \\ \\  
> 3 3
> 
> 示例 1：
> 
> 输入：root = \[1,2,2,3,4,4,3\]  
> 输出：true  
> 示例 2：
> 
> 输入：root = \[1,2,2,null,3,null,3\]  
> 输出：false  
> 
> 
> 限制：
> 
> 0 <= 节点个数 <= 1000
> 
> 来源：力扣（LeetCode）  
> 链接：https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof  
> 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

使用递归进行判断，判断同一层次中的二叉树节点是否对称。

首选排除 异常情况 以及 特殊情况。

所谓异常情况就是空节点的情况，

左右同时为null，

左为null或者右为null

两节点值不同

排除这些情况，那么剩下的只有一个答案

那就是两节点不为null且值相同。

能走到左右节点同时为 null 的程度，那么就说明走到了叶子节点，可以返回true了。

但一颗二叉树有两个节点，这两个节点必须都和另外的两个节点匹配才能说明对称，这两个条件必须同时成立才可以。

class Solution {
        public boolean isSymmetric(TreeNode root){
            // 递归前先判断
            if(root == null) {
                return true;
            }
            return compare(root.left,root.right);
        }
        boolean compare(TreeNode left,TreeNode right){
            // 递归前先判断，递归终止条件，先排除空节点 与 数值不同的情况
            // 排除之后，剩下的是就是非空节点 与 数值相同的情况了
            if(left == null && right == null){
                return true;
            }
            if(left == null || right == null || left.val != right.val){
                return false;
            }
            // 左节点的左节点与右节点的右节点相同，左节点的右节点和右节点的左节点相同，则对称
            // 确定递归参数 与 返回值
            boolean outside = compare(left.left,right.right);
            boolean inside = compare(left.right,right.left);
            return outside && inside;
        }
    }

--------------------

对于读书来说，书读的越多，读的越快。

当你积累了足够多的专业领域的知识，看到每一个专业的字词都可以快速地理解，那么在读书的时候就可以快速地向后推进。

读书分为结果导向式读书和漫游式读书

结果导向式就是带着问题去读书，通过读不同的书归纳总结出问题的答案。效果立竿见影。

漫游式读书顾名思义，就是随心阅读，这个是需要大量阅读的。这个需要积累。