0094. Binary Tree Inorder Traversal - chasel2361/leetcode GitHub Wiki

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

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

這個問題要求我們用 In-Order (中序) 的方式回傳二元樹的值，不論遞迴法或迭帶法都可以參考上一題講到的概念可以相當輕鬆的解決，程式碼如下

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

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

時間複雜度與空間複雜度皆為 O(N)

然後在討論區看到一個很狂的解法

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right) if root else []

也是遞迴法，一行解決有點帥XD