Day 11：94. Binary Tree Inorder Traversal

今日题目

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

前一篇Preorder Traversal分享完後，这次是Inorder Traversal观念题。若没看过前一篇，还是建议先往前看过Tree的观念及Preorder Traversal会更好。

简单说说 Inorder Traversal

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

1. Preorder
2. Inorder
3. Postorder

今天会用到的就是Inorder Traversal。
前一篇提到的Preorder原则是一进入节点就读这个值，而Inorder不一样的是第一次返回到节点才读这个值。假设资料是 tree = [5, 2, 6, 1, 3, null, 8]

上图中，每个节点上面的数字是读的顺序，而红色虚线箭头就是读的方向。Inorder排出来就会是 [1, 2, 3, 5, 6, 8]，Inorder读完的感觉是整棵树越左边的节点就会越先读到，换一种方式看如下图。

题目解说

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

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

约束：

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

范例1

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

范例2

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

范例3

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

范例4

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

范例5

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

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

解题的想像

文字描述

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

图解过程

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

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

1. step1 从根节点进入以後，会直接走到左边最底，回来以後的红色圆，是要开始纪录到list的第一个值。
2. step2 跟 step4 很像都是往右边子节点前进，再往下层发现左边子节点没有值，回到红色圈就是要纪录的值。
3. step3 当右子节点走完以後会一路往上走，回到根节点，这时也是对根节点来说，是左边的子节点走完了，因此要在这个时候纪录这个根节点到list。
4. step5 会把剩下的虚线节点走完，确认整棵树走过一次，再走回根节点结束这个Traversal。
5. 走完step1 ~ step5以後，就会组成step6看到的list，这个list是过程中出现的红色圆一个一个组成的，也就是Inorder Traversal最後要回传的结果。

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

程序码撰写

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

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

1. Inorder Traversal
2. 94. Binary Tree Inorder Traversal的解题方法

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

Next：145. Binary Tree Postorder Traversal