【剑指 の 精选】从宏观角度看「对称二叉树」问题 ｜Python 主题月

输入：{8,6,6,5,7,7,5}
返回值：true
复制代码

输入：{8,6,9,5,7,7,5}
返回值：false
复制代码

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;
    }
}
复制代码

from collections import deque
from math import inf
class Solution:
    emptyNode = TreeNode(inf)
    def isSymmetrical(self, root):
        if root is None:
            return True
        d = deque([])
        d.append(root)
        while d:
            # 每次循环都将下一层拓展完并存到「队列」中
            # 同时将该层节点值依次存入到「临时列表」中
            size = len(d)
            lt = []
            while size > 0:
                poll = d.popleft()
                if poll != self.emptyNode:
                    d.append(poll.left if poll.left is not None else self.emptyNode)
                    d.append(poll.right if poll.right is not None else self.emptyNode)
                size -= 1
                lt.append(poll.val)
            # 每一层拓展完后，检查一下存放当前层的该层是否符合「对称」要求
            if not self.check(lt):
                return False
        return True
    def check(self, lt):
        # 使用「双指针」检查某层是否符合「对称」要求
        l, r = 0, len(lt) - 1
        while l < r:
            if lt[l] != lt[r]:
                return False
            l += 1
            r -= 1
        return True
复制代码

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);
    }
}
复制代码

class Solution:
    def isSymmetrical(self, root):
        return self.check(root, root)
    def check(self, a, b):
        if a is None and b is None:
            return True
        elif a is None or b is None:
            return False
        if a.val != b.val:
            return False
        return self.check(a.left, b.right) and self.check(a.right, b.left)
复制代码