題目敘述 94. Binary Tree Inorder Traversal
題目給定一個二元樹的根結點。
請輸出中序拜訪(In-order traversal)的拜訪序列。
中序拜訪的定義:
1.拜訪左子樹。
2.拜訪目前的節點。
3.拜訪右子樹。
示意圖
測試範例
Example 1:
Input: root = [1,null,2,3]
Output: [1,3,2]
Example 2:
Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [4,2,6,5,7,1,3,9,8]
Example 3:
Input: root = []
Output: []
Example 4:
Input: root = [1]
Output: [1]
約束條件
Constraints:
- The number of the nodes in the tree is in the range [0, 100].
節點總數目介於0~100之間。
請注意，題目有可能給一個空樹。
- -100 <= Node.val <= 100
節點值都介於-100 ~ 100之間。
進階提問
Follow up: Recursive solution is trivial, could you do it iteratively?
遞迴的方式很簡單，請問你能使用迭代的方式完成後序拜訪嗎?
演算法 遞迴法 依據定義實現
其實不管是哪一層，哪一個節點，後序拜訪的規則都是相同的，
只要根據後序拜訪的定義，寫出遞迴function即可。
中序拜訪的定義:
1.拜訪左子樹。
2.拜訪目前的節點。
3.拜訪右子樹。
程式碼 遞迴法 依據定義實現
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
travarlsal_path = []
if root :
# just follow inorder definition
travarlsal_path.extend( self.inorderTraversal( root.left ) )
travarlsal_path .append( root.val )
travarlsal_path.extend( self.inorderTraversal( root.right) )
return travarlsal_path
複雜度分析
時間複雜度: O(n)
每個節點拜訪一次，總共n個節點。
空間複雜度: O(n)
每個節點拜訪一次，總共n個節點。
當整棵樹向左歪斜或者向右歪斜時，具有最大樹高O(n)，也是最深的遞迴深度。
程式碼 遞迴法 + python generator
對python generator概念和yield與unpacking *語法熟悉的讀者，
也可使用generator生成器的概念，直接在遞迴時動態輸出拜訪結果。
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
def inorder( node ):
## Base case on empty node or empty tree
if not node:
return
## General cases
yield from inorder(node.left)
yield node.val
yield from inorder(node.right)
return [*inorder( root )]
複雜度分析
時間複雜度: O(n)
每個節點拜訪一次，總共n個節點。
空間複雜度: O(n)
每個節點拜訪一次，總共n個節點。
當整棵樹向左歪斜或者向右歪斜時，具有最大樹高O(n)，也是最深的遞迴深度。
程式碼 迭代法 搭配stack
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
traversal_path = []
stack_inorder = [ (root, "init") ]
while stack_inorder:
current, label = stack_inorder.pop()
if not current:
# empty node
continue
elif label != "c":
# DFS with inorder
# left child, current node, right child,
# Stack is of Last In First Out,
# thus push in reverse of inorder
stack_inorder.append( (current.right, "r") )
stack_inorder.append( (current, "c") )
stack_inorder.append( (current.left, "l") )
elif label == "c":
traversal_path.append( current.val )
return traversal_path
複雜度分析
時間複雜度: O(n)
每個節點拜訪一次，總共n個節點。
空間複雜度: O(n)
每個節點拜訪一次，總共n個節點。
當整棵樹向左歪斜或者向右歪斜時，具有最大樹高O(n)，也是最長的stack長度。
結語
其實常見的tree traversal(前序、中序、後序拜訪)，
背後的核心觀念都是相同的。
Tree traversal其實就是探索整顆樹的搜索空間，也可以說是探索整顆樹，
只是指定順序略有不同而已。
有興趣的讀者可參考這篇文章，會用更宏觀的觀點看待樹的拜訪。
