乐趣区

关于算法:剑指-の-精选从宏观角度看对称二叉树问题

题目形容

这是「牛客网」上的 「JZ 58 对称的二叉树」,难度为 「艰难」

Tag :「剑指 Offer」、「二叉树」、「层序遍历」、「迭代」、「递归」

形容:

请实现一个函数,用来判断一棵二叉树是不是对称的。

留神,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。

示例 1

 输出:{8,6,6,5,7,7,5}

返回值:true

示例 2

 输出:{8,6,9,5,7,7,5}

返回值:false

要求:

  • 工夫:1 s
  • 空间:64 M

根本思维

首先要明确,题目所定义的“对称”是对每层而言,同时思考空节点。

因而,如果咱们应用惯例的遍历形式进行查看的话,须要对空节点有所示意。

部分查看(层序遍历)

咱们应用 0x3f3f3f3f 作为有效值,并建设占位节点 emptyNode 用来代指空节点(emptyNode.val = 0x3f3f3f3f)。

一个奢侈的做法是:应用「层序遍历」的形式进行「逐层查看」,对于空节点应用 emptyNode 进行代指,同时确保不递归 emptyNode 对应的子节点。

具体做法如下:

  1. 起始时,将 root 节点入队;
  2. 从队列中取出节点,查看节点是否为 emptyNode 节点来决定是否持续入队:
  • 当不是 emptyNode 节点时,将其左 / 右儿子进行入队,如果没有左 / 右儿子,则用 emptyNode 代替入队;
  • 当是 emptyNode 节点时,则疏忽;
  1. 在进行流程 的同时应用「长期列表」记录以后层的信息,并查看以后层是否合乎“对称”要求;
  2. 循环流程 和,直到整个队列为空。

代码:

import java.util.*;
class Solution {
    int INF = 0x3f3f3f3f;
    TreeNode emptyNode = new TreeNode(INF);
    boolean isSymmetrical(TreeNode root) {if (root == null) return true;

        Deque<TreeNode> d = new ArrayDeque<>();
        d.add(root);
        while (!d.isEmpty()) {
            // 每次循环都将下一层拓展完并存到「队列」中
            // 同时将该层节点值顺次存入到「长期列表」中
            int size  = d.size();
            List<Integer> list = new ArrayList<>();
            while (size-- > 0) {TreeNode poll = d.pollFirst();
                if (!poll.equals(emptyNode)) {d.addLast(poll.left != null ? poll.left : emptyNode);
                    d.addLast(poll.right != null ? poll.right : emptyNode);
                }
                list.add(poll.val);
            }
            
            // 每一层拓展完后,检查一下寄存以后层的该层是否合乎「对称」要求
            if (!check(list)) return false;
        }
        return true;
    }

    // 应用「双指针」查看某层是否合乎「对称」要求
    boolean check(List<Integer> list) {int l = 0, r = list.size() - 1;
        while (l < r) {if (!list.get(l).equals(list.get(r))) return false;
            l++;
            r--;
        }
        return true;
    }
}
  • 工夫复杂度:在层序遍历过程中,每个节点最多入队一次,同时在 check 查看对称性过程中,每层只会被查看一次。复杂度为
  • 空间复杂度:

整体查看(递归)

在「层序遍历」解法中,咱们利用了“对称”定义对每层进行查看。

实质上这是利用“对称”定义进行屡次「部分」查看。

事实上,咱们还能够利用“对称”定义在「整体」层面上进行查看。

咱们如何定义两棵子树 ab 是否“对称”?

当且仅当两棵子树合乎如下要求时,满足“对称”要求:

  1. 两棵子树根节点值雷同;
  2. 两颗子树的左右子树别离对称,包含:
  • a 树的左子树与 b 树的右子树相应地位的值相等
  • a 树的右子树与 b 树的左子树相应地位的值相等

具体的,咱们能够设计一个递归函数 check,传入待检测的两颗子树的头结点 ab(对于本题都传入 root 即可),在单次查问中有如下不言而喻的判断子树是否“对称”的 Base Case:

  • ab 均为空节点:合乎“对称”要求;
  • ab 其中一个节点为空,不合乎“对称”要求;
  • ab 值不相等,不合乎“对称”要求;

其余状况,咱们则要别离查看 ab 的左右节点是否“对称”,即递归调用 check(a.left, b.right)check(a.right, b.left)

代码:

class Solution {public boolean isSymmetrical(TreeNode root) {return check(root, root);
    }
    boolean check(TreeNode a, TreeNode b) {if (a == null && b == null) return true;
        if (a == null || b == null) return false;
        if (a.val != b.val) return false;
        return check(a.left, b.right) && check(a.right, b.left);
    }
}
  • 工夫复杂度:每个节点只会被拜访一次。复杂度为
  • 空间复杂度:

总结

上述两种解法不仅仅是实现上的不同,更多的是查看“出发点”的不同:

  • 解法一:利用「层序遍历」的形式,以“层”为单位进行“对称”查看;
  • 解法二:利用「递归树开展」的形式,以“子树”为单位进行“对称”查看。

当咱们从整体层面登程思考时,配合递归,往往能写出比惯例做法要简洁得多的代码。

倡议大家加深对「部分」和「整体」两种不同出发点的了解。

最初

这是咱们「剑指 の 精选」系列文章的第 58 篇,系列开始于 2021/07/01。

该系列会将「剑指 Offer」中比拟经典而又不过时的题目都讲一遍。

在提供谋求「证实」&「思路」的同时,提供最为简洁的代码。

欢送关注,交个敌人 (`・ ω ・´)

退出移动版