长大后想做什么？做回小孩！

0%

LeetCode——对称二叉树

发表于 更新于 分类于 Valine：
本文字数： 297

NO.101 对称二叉树 简单

GH2RgK.png

思路一：递归实现 判断二叉树是否对称，就是判断结构是否对称和对称节点值是否相等。就是判断根的左右子树是否对称，子树继续递归判断子树根的左右子树是否对称。

1
2
3
4
5
6
7
8
9
10
11
12
public boolean isSymmetric(TreeNode root) {
    return isMirror(root, root);
}

private boolean isMirror(TreeNode root, TreeNode root1) {
    //判断结构是否对称
    if (root == null && root1 == null) return true;
    if (root == null || root1 == null) return false;
    return root.val == root1.val//结构对称，对称节点的值是否相等。
        && isMirror(root.left, root1.right)//左子树和右子树
        && isMirror(root.right, root1.left);//右子树和左子树
}

时间复杂度：O(n) 遍历树的节点。

思路二：迭代实现 很容易理解，但是第一次实现的时候依然很棘手。

借助一个队列，初始化入队根节点两次。判断的过程中每次出队两个节点r1、r2，这两个节点是镜像节点，所以应该是相等的，否则树不对称；过程像是层序遍历一样，但是每次入队r1的left和r2的right以及r1的right和r2的left。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean isSymmetric(TreeNode root) {
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode r1 = queue.poll();
        TreeNode r2 = queue.poll();
        if (r1 == null && r2 == null) continue;//结构一样
        if (r1 == null || r2 == null) return false;//结构不同
        if (r1.val != r2.val) return false;//对称节点值不同
        //将镜像节点入队
        queue.add(r1.left);
        queue.add(r2.right);
        queue.add(r1.right);
        queue.add(r2.left);
    }
    return true;
}

时间复杂度：O(n) 遍历节点

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github