LeetCode 94. Binary Tree Inorder Traversal
# 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]:
ans = []
if root is None:
return []
def addList(node):
if node.left:
addList(node.left)
ans.append(node.val)
if node.right:
addList(node.right)
return ans
return addList(root)
inorder traversal
あるノードに対して左側の要素、ノード自身、右側の要素の順にアクセスされる探索方法
例えば…
in : [4,2,6,1,3,5,7]
out : [1,2,3,4,5,6,7]
→二分木の要素が小さい順にアクセスできる!!
小さい順にアクセスできるという特徴を生かして
530. Minimum Absolute Difference in BST
が解けたりする