LeetCode-101. 对称二叉树

偏执的太偏执、 2024-03-27 15:39 53阅读 0赞

#### 目录 ####

*   *  题目分析
     *  递归法

题目来源  
[101. 对称二叉树][101.]

### 题目分析 ###

首先想清楚，判断对称二叉树要比较的是哪两个节点，要比较的可不是左右节点！

对于二叉树是否对称，要比较的是根节点的左子树与右子树是不是相互翻转的，理解这一点就知道了其实我们要比较的是两个树（这两个树是根节点的左右子树），所以在递归遍历的过程中，也是要同时遍历两棵树。

那么如何比较呢？  
比较的是两个子树的里侧和外侧的元素是否相等。如图所示：  
![在这里插入图片描述][313a70a3e43444b392c5f4ef74767731.png]  
那么遍历的顺序应该是什么样的呢？

本题遍历只能是“后序遍历”，因为我们要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否相等。

正是因为要遍历两棵树而且要比较内侧和外侧节点，**所以准确的来说是左树的遍历顺序是左右中，右树的遍历顺序是右左中。**

### 递归法 ###

**递归三部曲**

*  1.确定递归函数的参数和返回值  
    因为我们要比较的是根节点的两个子树是否是相互翻转的，进而判断这个树是不是对称树，所以要比较的是两个树，参数自然也是左子树节点和右子树节点。

boolean compare(TreeNode left,TreeNode right)

*  2.确定终止条件  
    要比较两个节点数值相不相同，首先要把两个节点为空的情况弄清楚！否则后面比较数值的时候就会操作空指针了。  
    节点为空的情况有：（注意我们比较的其实不是左孩子和右孩子，所以如下我称之为左节点右节点）
    
     *  左节点为空，右节点不为空，不对称，return false
     *  左不为空，右为空，不对称 return false
     *  左右都为空，对称，返回true
     *  左右都不为空，比较节点数值，不相同就return false

// 首先排除空节点的情况
            if (left == null && right != null){
        
                return false;
            } else if (left != null && right == null) {
        
                return false;
            }else if (left == null && right == null) {
        
                return true;
            // 排除了空节点，再排除数值不相同的情况
            }else if (left.val != right.val){
        
                return false;
            }

*  3.确定单层递归的逻辑  
    此时才进入单层递归的逻辑，单层递归的逻辑就是处理 左右节点都不为空，且数值相同的情况。
    
     *  比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
     *  比较内测是否对称，传入左节点的右孩子，右节点的左孩子。
     *  如果左右都对称就返回true ，有一侧不对称就返回false 。

// 此时就是：左右节点都不为空，且数值相同的情况
            // 此时才做递归，做下一层的判断
            boolean outside = compare(left.left,right.right);   // 左子树：左、 右子树：右
            boolean inside = compare(left.right,right.left);    // 左子树：右、 右子树：左
            // 左子树：中、 右子树：中 （逻辑处理）
            boolean result = outside && inside;

**代码实现**

class Solution {
        
        public boolean isSymmetric(TreeNode root) {
        
            if(root == null){
        
                return true;
            }
            return compare(root.left,root.right);
        }
    
        public static boolean compare(TreeNode left,TreeNode right){
        
            // 首先排除空节点的情况
            if (left == null && right != null){
        
                return false;
            } else if (left != null && right == null) {
        
                return false;
            }else if (left == null && right == null) {
        
                return true;
            // 排除了空节点，再排除数值不相同的情况
            }else if (left.val != right.val){
        
                return false;
            }
    
            // 此时就是：左右节点都不为空，且数值相同的情况
            // 此时才做递归，做下一层的判断
            boolean outside = compare(left.left,right.right);   // 左子树：左、 右子树：右
            boolean inside = compare(left.right,right.left);    // 左子树：右、 右子树：左
            // 左子树：中、 右子树：中 （逻辑处理）
            boolean result = outside && inside;
            return result;
    
        }
    }

![在这里插入图片描述][fcaccd9e2b97481cb8b50fe9b7b5f34b.png]  
[LeetCode-100. 相同的树][LeetCode-100.]  
[LeetCode-572. 另一棵树的子树][LeetCode-572.]

[101.]: https://leetcode.cn/problems/symmetric-tree/
[313a70a3e43444b392c5f4ef74767731.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/4de725546483441394b580ddd1a6d040.png
[fcaccd9e2b97481cb8b50fe9b7b5f34b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/0deb5e852253459985360088590fe760.png
[LeetCode-100.]: https://donglin.blog.csdn.net/article/details/128985423
[LeetCode-572.]: https://donglin.blog.csdn.net/article/details/128985660