发表于

「这是我参与11月更文挑战的第9天，活动详情查看：2021最后一次更文挑战」。

对称二叉树是我们数据结构中常用的一类数据结构，今天我们使用算法来对其进行校验什么样的树称得上对称二叉树。

题目描述

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

题目示例

题目解法

解法一：递归实现（推荐）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
kotlin复制代码/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
 /**
  * 递归实现
  */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        return validateNode(root.left, root.right);
    }

    public boolean validateNode(TreeNode left, TreeNode right){
        if(left == null && right == null){
            return true;
        }
        if(left == null || right == null){
            return false;
        }
        if(left.val != right.val){
            return false;
        }
        // 递归实现
        return validateNode(left.left, right.right) && validateNode(left.right, right.left);
    }
}

解法二：迭代实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
csharp复制代码/**
  * 迭代实现
  */
class Solution {
    
    public boolean isSymmetric(TreeNode root) {
        return validate(root.left, root.right);
    }

    public boolean validate(TreeNode left, TreeNode right){
        if (left == null && right == null){
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(left);
        queue.add(right);
        // 迭代判空
        while (!queue.isEmpty()){
            TreeNode q = queue.poll();
            TreeNode p = queue.poll();
            if (q == null && p == null){
                continue;
            }
            if (q == null || p == null){
                return false;
            }
            if (q.val != p.val){
                 return false;
            }
            queue.add(q.left);
            queue.add(p.right);

            queue.add(q.right);
            queue.add(p.left);
        }
        return true;
    }
}

LeetCode原题链接：leetcode-cn.com/problems/sy…

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%