Day 15：101. Symmetric Tree

今日题目

题目连结：101. Symmetric Tree
题目主题：Tree, Depth-First Search, Breadth-First Search, Binary Tree

简单说说 Traversal

Traversal 已经在前几天差不多都提过了，但这边想再分享一下，其实 Traversal 是可以简单分为两种方向，从左节点开始走或从右节点开始走，在前面的文章中都是以左边节点开始走的范例，今天也在复习一下每一种Traversal的差别，这里分享一下从左边及从右边开始走的运作范例：

假设资料：tree = [5, 2, 6, 1, 3, null, 8]

Preorder Traversal

Inorder Traversal

Postorder Traversal

Levelorder Traversal

这边特别提一下 Inorder Traversal 有趣的状况，范例因为刚好是 Binary Search Tree，所以可以发现从左先走会排出一个从小到大的顺序 [1, 2, 3, 5, 6, 8]、从右先走会排出一个从大到小的顺序 [8, 6, 5 ,3, 2, 1]。如果还不知道什麽是 Binary Search Tree 没关系， 下一篇将会开始会分享 Binary Search Tree 的主题。

题目解说

建议可以看看LeetCode原本的题目说明，这边是用我的方式说明题目，参考就好。

题目会给一颗二元树，目标是确认这棵树是不是两边节点长的一样的对称树，像是照镜子一样，参考下面从Leetcode上面截取的范例图：

如果是一颗对称树将会回True，若不是对称树则回传False，下面是从Leetcode上面截取非对称树的范例图：

约束：

• 树的节点总数范围在[1, 1000]
• -100 <= Node.val <= 100

范例1

输入：root = [1,2,2,3,4,4,3]
输出：true
解说：参考题目解说的第一张图。

范例2

输入：root = [1,2,2,null,3,null,3]
输出：false
解说：参考题目解说的第二张图。

建议到这边先停下来，尝试自己解解看，若没有想法可再继续走下去。

解题的想像

文字描述

1. 若根节点没有子节点，直接回传True结束
2. 使用Level-Order Traversal来实作
3. 宣告两个Queue，一个往左边走，一个往右边走
4. 跑一个回圈，直到两边都把全部节点走完：
   • 每一圈分别跟两边各取一个节点
   • 确认是否两边都有节点，若其中一边没节点，代表非对称直接回传False结束
   • 确认里面的值是否相同，若不同代表非对称，直接回传False结束
   • 若目前都对称且还有子节点，分别放进两边的Queue，继续回圈
5. 若全部节点都走完，代表这是一个对称树，回传True

图解过程

范例：root = [1, 2, 2, 3, 4, 5, 3]

上图中，一开始我们先宣告两个Queue，用来实现Level-Order Traversal使用的，因为需要两边同时走，所以宣告分别为 leftQueue 及 rightQueue 。若根节点没有子节点会直接回传True，可以看到范例是有子节点的，所以两边 Queue 直接从第二层节点开始走。

上图是回圈的运作过程，橘黄色方框是目前走到的节点，可以看到左边跟右边同时会取得一个来确认目前是不是对称的，确认完会继续将下层节点放到 Queue 中准备。

可以观察 step1 ，左边跟右边走的方向也会不一样，左边是优先走左边 3 节点在走 4 节点，而右边是优先走右边 3 节点在走 5 节点。

最後会在 step3 读到最後一个节点发现，这不是一颗对称的树，左边节点读到的是 4，右边节点读到的是 5，所以最後这个范例是回传 False。

若因为没想法而走到这边，建议看完想像以後再给自己一次机会试一次。

程序码撰写

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        # 若根节点没有子节点，直接回传True结束
        if not root.left and not root.right:
            return True
        
        # 使用Level-Order Traversal的方式走
        # 准备两个Queue，左边及右边同时一起走
        leftQueue = deque()
        rightQueue = deque()
        leftQueue.append(root.left)
        rightQueue.append(root.right)
        
        # 若两边都走到没节点，结束这个回圈
        while len(leftQueue) > 0 and len(rightQueue) > 0:
            # 取出左边及右边节点
            left = leftQueue.popleft()
            right = rightQueue.popleft()
            # 其中一个有节点，另一边没节点，直接回传False结束
            if (left and not right) or (right and not left):
                return False
            # 若两边都有节点
            if left and right:
                # 确认两边值是否不同，不同直接回传False结束
                if left.val != right.val:
                    return False
                else:
                    # 把子节点放进Queue继续回圈
                    leftQueue.append(left.left)
                    leftQueue.append(left.right)
                    rightQueue.append(right.right)
                    rightQueue.append(right.left)
        # 全部走完，代表这是一个对称树
        return True

希望您今天能了解到...

1. Traversal 左边走及右边走的过程
2. 101. Symmetric Tree 的解题方法

若内容有什麽问题或建议欢迎一起交流：）
感谢您今天愿意花时间看完这篇文章~~~~

Next：108. Convert Sorted Array to Binary Search Tree