0144. Binary Tree Preorder Traversal - chasel2361/leetcode GitHub Wiki

Given a binary tree, return the preorder traversal of its nodes' values.

Example:
Input: [1,null,2,3]
Output: [1,2,3]

這題的目標是以 Preorder 的順序來尋訪整個二元樹，如果用遞迴法會比較直觀

class Solution:
    def __init__(self):
        self.traversal = []
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root: return []
        
        self.traversal.append(root.val)        
        self.preorderTraversal(root.left)            
        self.preorderTraversal(root.right)
        
        return self.traversal

迭代法的部分需要使用 stack 的概念來把暫時還沒用到的節點儲存進去，由於 Preorder 是以"根 - 左 - 右"的順序尋訪，因此進入 stack 的順序會是"右 - 左 - 根"，每往前一步就將當前節點的值輸出

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        traversal = []
        stack = [root]
        if not root: return traversal
            
        while stack:
            node = stack.pop()
            if node.right: 
                stack.append(node.right)
            if node.left: 
                stack.append(node.left)
            traversal.append(node.val)
        return traversal

這兩種寫法的時間與空間複雜度都是 O(N)