94. Binary Tree Inorder Traversal

Loading...LeetCode

DFS inorder，没想到iteratively写起来还挺麻烦，需要先遍历到底再开始记录值。recursively就没啥区别了，可以看Q144的preorder对比。

144. Binary Tree Preorder Traversal

iteratively

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root: return []
        
        stack = collections.deque([])
        res = []
        cur = root
        while stack or cur:
            while cur:
                stack.append(cur)
                cur = cur.left
            cur = stack.pop()
            res.append(cur.val)
            cur = cur.right
            
        return res

recursively

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        
        def inorder(node, res):
            if not node: return
            inorder(node.left, res)
            res.append(node.val)
            inorder(node.right, res)
        
        inorder(root, res)
        return res