【第十九天 - Binary Tree题目分析】

先简单回顾一下，今天预计分析的题目：94. Binary Tree Inorder Traversal

题目叙述：https://leetcode.com/problems/binary-tree-inorder-traversal/

题目叙述：

• 题目会给一个二元树结构的资料
  

测资的 Input/Output

• 会给一个指向 root 的资料
• 回传中序排列
  

二元树主要有四种遍历/走访(traversal) binary tree 的方法，分别为：

• 前序遍历 (Preorder Traversal)
• 中序遍历 (Inorder Traversal)
• 後序遍历 (Postorder Traversal)
• 层序遍历 (Level-order Traversal)

参考资料：https://ithelp.ithome.com.tw/articles/10205571

这边针对中序进行简单的介绍：

• 中序(inorder) 是一种遍历/走访(traversal) binary tree 的方法，对於任意节点，先走左侧的 sub-tree，再走当前节点，最後走右侧 sub-tree。

• 以此图为例， inorder traversal 便会是 2→ +→ 3→ x→ 7
  

  • 从 root 开始，先走左侧子树，再走 x ，再走 7
    

  • 左侧子树的走法也是同样道理，先走 2 ，再走 + ，最後走 3
    

  • 因此整个顺序如下
    

实作方法

• 递回

  • 我们可以用 DFS 轻松实现中序走访，首先开一个 list 存放答案

  ans = []
  

  • 使用递回方式实作，首先确定终止条件： 当节点为 None，则停止。

  if node == None:
      return None
  

  • 若节点存在，则先走访左侧子树

  traverse(node.left)
  

  • 接着走访当前节点。本题需要 return 一个 list ，其中依照 inorder 顺序存放节点的值，因此当走访一个节点时，只需要将 value 存入 list 即可。

  ans.append(node.val)
  

  • 最後走访右侧子树

  traverse(node.right)
  

  • 完整 Code 如下

  class Solution:
      def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
          ans = []
          def traverse(node):
              if node == None:
                  return None
  
              traverse(node.left)
              ans.append(node.val)    
              traverse(node.right)
  
          traverse(root)
          return ans
  

• 迭代

  • 程序逻辑
    1. 使用回圈，先走访该点的左 child 走到底，经过的节点都储存於 stack 中
    2. 经历过步骤1，拿出 stack 中资料，此节点会是尚未走访过的左 child，我们将此点的 value 储存於 ans 中 ( 因为中序是先读取 左child → parent → 右child )
    3. 接着看该点的 右 child，并重复 1~3 步骤，直到走访完全部的 Binary Tree
  • python 实作

  class Solution:
      def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
          stack = []
          ans = []
  #       当 root 与 stack 都为空，代表走访完整个二元树
          while root or stack:
  #           不断走访左child，直到树的最左下角，每次走访都存入 stack 中
              while root:
                  stack.append(root)
                  root = root.left
  #           将储存在 stack 的资料拿出来
              root = stack.pop()
  #           ans 储存 root.val
              ans.append(root.val)
  #           换走访 root 的 右 child 
              root = root.right
          return ans