[leetcode] 94. Binary Tree Inorder Traversal

원문)

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

번역)

이진트리를 주어졌을때 그 노드값을 inorder 순회를 반환하라.


예제)

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]

문제접근)

자식의 왼쪽 자식 -> 부모 -> 오른쪽 자식

이내용은 top-down은 쉽게 했는데 bottom-up은 고민했다.
왼쪽을 최우선으로 다 훑고 부모값을 지나 그 후에 우측자식노드를 훑는다고 생각하고 작업해보자.


코드)

1.  top-down

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # top-down def inorderTraversal(self, root: TreeNode) -> List[int]: answer = [] self.top_down(root, answer) return answer def top_down(self, root: TreeNode, answer: List[int]): if root is None: return self.top_down(root.left, answer) answer.append(root.val) self.top_down(root.right, answer)

2. bottom-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # bottom-down def inorderTraversal(self, root: TreeNode) -> List[int]: answer = [] stack = [] cur = root while True: while cur: stack.append(cur) cur = cur.left if stack: cur = stack.pop() answer.append(cur.val) cur = cur.right else: break return answer