Day 14：965. Univalued Binary Tree

今日题目

题目连结：965. Univalued Binary Tree
题目主题：Tree, Depth-First Search, Breadth-First Search, Binary Tree

Traversal 除了在 Depth-First Search 中会看到的Preorder、Inorder、Postorder以外，另外还有一种叫做Level-Order Traversal，通常在Breadth-First Search主题中使用到。

简单说说 Level-Order Traversal

Level-Order Traversal通常会在Breadth-First Search主题中看到，原则就是以层级的方式一层一层往下读取，运作过程如下图：

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

上图中，每个节点上面的数字是读的顺序，而红色虚线箭头就是读的方向。这边满单纯的，可以看到就是从最上层，一层一层照顺序读下来，Level-Order排出来顺序就会是 [5, 2, 6,1, 3, 8]，通常会使用Queue来实作，若还没了解过Queue的夥伴建议也可以先看看本系列文 Day 6：232. Implement Queue using Stacks 的简单说说 Queue。

题目解说

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

本题会给一颗二元树，目的是要确认，这棵树的所有节点是否全部都是同样的一个值，如果全部节点的值都一样会回传True，只要有一个值不同，就会回传False。

约束：

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

范例1

输入：root = [1,1,1,1,1,null,1]
输出：true
解说：可以看到输入的树，全部都是1，所有的节点值都相同，因此回True。

范例2

输入：root = [2,2,2,5,2]
输出：false
解说：输入的树中几乎都是2，但其中出现了一个 5，有节点的值不一样，因此回False。

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

解题的想像

文字描述

1. 把根节点的值先记录下来，用来判断每个节点是否为相同值。
2. 宣告一个Queue来实作Level-Order Traversal。
3. 将根节点先放入Queue中。
4. 跑一个回圈，直到每个节点都走过一次：
   • 每一圈都会取得目前读到的节点。
   • 将目前节点的值跟第 1 步骤记录的根节点值确认是否相同。
   • 若不同直接回传 False 结束，代表这棵树已经不是全部节点的值都相同。
   • 若相同继续确认是否还有节点，如果还有节点，将节点都放进Queue继续回圈。
5. 若全部节点都相同，回传True结束。

图解过程

范例：root = [5, 5, 5, null, 4]

上图中，绿色方框是一开始要纪录的根节点值，也是用来跟之後每个节点值确认是否相同的值。而中间的Queue就是用来实作 Level-Order Traversal用的，在这边已经先把根节点放进去了。

上图是回圈运作的过程，每一圈都会取得一个橘黄色方框，这个橘黄色方框是目前读到的节点，而红色方框就是橘黄色方框的子节点，会先放进Queue中预备。

每一圈都会检查目前的节点的值跟绿色方框根节点的值是否相同，若相同会继续走下去。另外可以看 step3 及 step4，因为目前读到的橘黄色方框都没有子节点，所以不用作append的动作。step4 这个步骤也检查到有节点的值与根节点值不同，因此这个范例的结果会回传 False。

最後也可以观察一下 step1 ~ step4 的橘黄色方框，读的顺序就跟前面分享 Level-Order Traversal 走的顺序是相同的，这就是用 Queue 实作 Level-Order Traversal 的过程。

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

程序码撰写

class Solution:
    def isUnivalTree(self, root: Optional[TreeNode]) -> bool:
        # 纪录根节点的值
        value = root.val
        # 使用Queue来实作 Level-Order Traversal
        queue = deque()
        # 从根节点开始读
        queue.append(root)
        
        # Queue 走到 0 代表全部节点都读过
        while len(queue) > 0:
            # 每圈读取一个节点
            node = queue.popleft()
            # 检查这个值是否与根节点值不同，若不同直接回传False结束
            if node.val != value:
                return False
            # 若还有子节点，放进Queue，让回圈继续走完每个节点
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        return True

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

1. Level-Order Traversal
2. 965. Univalued Binary Tree 的解题方法

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

Next：101. Symmetric Tree