Day 10：144. Binary Tree Preorder Traversal

今日题目

题目连结：144. Binary Tree Preorder Traversal
题目主题：Stack, Tree, Depth-First Search, Binary Tree

前一篇提到了Heap是一个Tree的结构，这次开始正式进入Tree的世界。今天要分享如何想像 Tree 的样子，学习如何读这颗树的资料。而接下来的三个题目我们是用 Depth-First Search 深度优先的方式来解题。

简单说说 Tree

接下来会有很多题目会看到像下图这样的注解：

这是在说明一个树的节点长什麽样子，称它TreeNode，每个节点会有三个属性。

1. val：这个节点的值。
2. left：是一个TreeNode，这个节点的子层左节点。
3. right：是一个TreeNode，这个节点的子层右节点。

以下是一个范例，可以这样想像：

上图中，黑色的方框是一个TreeNode，可以看到他实际的val是5，左边红色方框是 left 子层左节点(TreeNode)，右边绿色方框是 right 子层右节点(TreeNode)。再以红色方框的TreeNode为例，这是一个没有子层右节点的TreeNode，这样的状况是有可能的。当然这只是一个范例，实际上一棵树可能长的更大，最下层的 2 这个子节点下面可能还有一个left节点跟right节点这样长下去。

另外要提的是，接下来给的题目，都会给这样的范例，如下图：

所以在这边也要先分享，如何将一个阵列看成一棵树？拿昨天的范例当例子。

实际上这棵树转成阵列以後，会长这个样子：
tree = [1, 4, 6, 14, 13, 11, 16]
那如果没有这个图，只有阵列时，应该要怎麽看呢？

如上图，每一层有多少数量就是用 2 的次方来看。
第一层是 2 的 0 次方，只有一个，而这个就是树的根节点。
第二层是 2 的 1 次方是2，所以有两个元素，分别是根节点的子层左节点及子层右节点。
第三层是 2 的 2 次方总共有四个，从左边排到右边，14、13 就是 4 的子节点，11、16就是6的子节点。
假设这棵树继续长第四层，就会是 2 的 3 次方，总共会有8个节点，依此类推。
最後再看一次对应图。

简单说说 Preorder Traversal

在DFS（Depth-First Search）中Traversal分成三种方式：

1. Preorder
2. Inorder
3. Postorder

今天会用到的就是Preorder Traversal。
Preorder的原则就是，进入一个节点时，马上读取它的值，假设资料是 tree = [5, 2, 6, 1, 3, null, 8]

上图中，每个节点上面的数字是读的顺序，而红色虚线箭头就是读的方向。
Preorder排出来就会是 [5, 2, 1, 3, 6, 8]。

题目解说

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

今天的题目，目标就是用Preorder的方式来读取树，依照Preorder的顺序将节点的值排到一个列表中，最後回传这个列表。

约束：

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

范例1

输入: root = [1,null,2,3]
输出: [1,2,3]

范例2

输入: root = []
输出: []

范例3

输入: root = [1]
输出: [1]

范例4

输入: root = [1,2]
输出: [1,2]

范例5

输入: root = [1, null, 2]
输出: [1,2]

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

解题的想像

文字描述

1. 写一个递回方法，这个方法要能传入前往的节点及要完成的list。
2. 每呼叫一次这个方法会往一个节点前进，
3. 这个递回会一直到走到发现没有节点才会往回走。
4. 每进入一个节点的当下会将目前节点的值纪录到list中。
5. 最终跑完所有节点会回传一份用Preorder排出来的list。

图解过程

范例：tree = [5, 2, 6, null, 8]

下图中是实际上Traversal在走的过程，实际在想像移动过程的时候，建议在最下面的节点都补虚线的节点代表走到底了。

1. step1 及 step2都直接进入了一个新节点，红色圆就是目前要纪录到list的数字。
2. step3 及 step4实际走到一个红色圆，都有一个路径，这个路径是实际上走到红色圆之前会先经过的节点。
3. step5 会把剩下的虚线节点走完，确认整棵树走过一次，再走回根节点结束这个Traversal。
4. 走完step1 ~ step5以後，就会组成step6看到的list，这个list是过程中出现的红色圆一个一个组成的，也就是Preorder Traversal最後要回传的结果。

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

程序码撰写

class Solution:
    # root 要进入的节点
    # preorder_list 最终要回传的list
    def traversal(self, root: TreeNode, preorder_list: List[int]):
        # 没有节点往回走
        if root == None: return preorder_list
        # 进入节点纪录目前的值
        preorder_list.append(root.val)
        # 前往左边子节点
        preorder_list = self.traversal(root.left, preorder_list)
        # 前往右边子节点
        preorder_list = self.traversal(root.right, preorder_list)
        return preorder_list
    
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        return self.traversal(root, [])

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

1. TreeNode的长相
2. 将阵列看成一个树的结构
3. Preorder Traversal
4. 144. Binary Tree Preorder Traversal的解题方法

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

Next：94. Binary Tree Inorder Traversal