LeetCodeを1日1題解いてみる (day16)

16日目に取り組んだ問題はこちら！

94. Binary Tree Inorder Traversal

問題文

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

僕の回答

難しくて何もわからなかったのでGPTにコードを書いてもらい、解説をしてもらいながら実装しました。

# 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: Optional[TreeNode]) -> List[int]:
        stack = []. # 待ちノード
        result = []
        curr = root

        while stack or curr:

            while curr:  # 右の最深部までいく
                stack.append(curr)
                curr = curr.left
            
            curr = stack.pop()  # 末尾から取り出す
            result.append(curr.val)
            
            curr = curr.right  # 左に進む
        
        return result

より効率の良い回答例

特にありませんでした。

コメント

木の操作は理解が浅いと実感した。授業で木構造のアルゴリズムは習っていたのでしっかり理解したい。

次の問題はこちら!