Day 13：100. same tree

今日题目

题目连结：100. same tree
题目主题：Tree, Depth-First Search, Breadth-First Search, Binary Tree

在练习过Preorder、Inorder、Postorder三种Traversal以後，今天找了一题最後再来练习一下Depth-First Search主题。

简单说说 Tree Visualizer

虽然在前几篇都练习过如何把一个阵列看成一棵树，但这边可以分享一下，如果今天懒得自己想像Tree的样子，可以用Leetcode提供的功能来显示。

如上图，可以在Testcase的地方，开启Tree Visualizer，这时候上面就会出现一棵树的形状，下方的框框也会有蓝色的一条做标示，告诉你现在这棵树是用哪个阵列形成的。

题目解说

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

题目会给两棵树，分别为 p 及 q，目标是检查这两棵树是否所有TreeNode都是一样的，若都是一样的回传True，若不一样就回传False。

约束：

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

范例1

输入: p = [1,2,3], q = [1,2,3]
输出: true

范例2

输入: p = [1,2], q = [1,null,2]
输出: false

范例3

输入: p = [1,2,1], q = [1,1,2]
输出: false

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

解题的想像

文字描述

1. 写一个递回方法，这个方法会传两棵树目前要前往的TreeNode。
2. 每次呼叫这个方法，前往的节点两边会是同步的。
3. 用Preorder的方式，每进入一个节点直接检查当下节点是否为相同，检查的状态有以下：
   • 目前节点都为空，代表目前都相同，继续检查下一个节点
   • 目前节点一个为空、一个不为空，代表两棵树已经不同了
   • 目前节点都有值，但值不相同，代表两棵树已经不同了
4. 全部节点都走完，并且过程中都没有出现不同的节点，代表最终两棵树是相同长相的树。

图解过程

范例: p = [1,2,3], q = [1,2,3]

如上图，检查两棵树是否一样，这次是用Preorder Traversal来实作，也就是进入一个节点就检查，可以看到step1 ~ step4 基本上都是，两边的树 p 跟 q 都是同时在前进的，过程中每一步都会去确认目前两颗树的节点是否相同，即便是绿色圆这个路径的每一步都会确认是否相同，一直到整棵树都走过一次没有不一样，最终就是回传True。

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

程序码撰写

class Solution:
    def sameNode(self, p: TreeNode, q: TreeNode):
        # 目前节点都为空
        if p == None and q == None:
            return True
        # 检查 两种状况都代表树长的不同
        # 1. 目前节点是否一个为空、一个不为空
        # 2. 两个都有节点但值不一样
        if ((p != None and q == None)
         or (p == None and q != None)
         or (p.val != q.val)):
            return False
        # 若已经检查到有一个节点不相同，直接结束这个递回
        if not self.sameNode(p.left, q.left):
            return False
        # 若已经检查到有一个节点不相同，直接结束这个递回
        if not self.sameNode(p.right, q.right):
            return False
        # 节点都相同才会走到这
        return True
    
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        return self.sameNode(p, q)

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

1. Tree Visualizer 的用法
2. 100.same tree 的解题方法

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

Next：965. Univalued Binary Tree