leetcode : Binary Tree Inorder Traversal

https://leetcode.com/problems/binary-tree-inorder-traversal/

Binary Tree Inorder Traversal - LeetCode

 

난 이거 혼자힘으로 못풀었다.

def inorderTraversal(self, root):
    res, stack = [], []
    while True:
        while root:
            stack.append(root)
            root = root.left
        if not stack:
            return res
        node = stack.pop()
        res.append(node.val)
        root = node.right

왼쪽으로 쭉 내려간다음에 더 내려갈 곳 없으면 pop해서 값 append하고 right subtree가 있다면 거기로 가서 또 쭈욱 왼쪽으로 내려가고..

 

어떻게 이런 생각을 했을까