94. Binary Tree Inorder Traversal

---

Description

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

 

Example 1:

Input: root = [1,null,2,3]

Output: [1,3,2]

Explanation:

Example 2:

Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]

Output: [4,2,6,5,7,1,3,9,8]

Explanation:

Example 3:

Input: root = []

Output: []

Example 4:

Input: root = [1]

Output: [1]

 

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

 

Follow up: Recursive solution is trivial, could you do it iteratively?

---

Code

package main

import "fmt"

type TreeNode struct {
	Val int
	Left *TreeNode
	Right *TreeNode
}

func inorderTraversal(root *TreeNode) []int {
	var result []int

	var dfs func(node *TreeNode)

	dfs = func(node *TreeNode) {
		if node == nil {
			return
		}

		dfs(node.Left)
		result = append(result, node.Val)
		dfs(node.Right)
	}

	dfs(root)
	return result
}

func main() {
	// 예제 트리 생성:   1
	//                   \
	//                    2
	//                   /
	//                  3
	root := &TreeNode{1, nil, &TreeNode{2, &TreeNode{3, nil, nil}, nil}}

	// 중위 순회 실행
	fmt.Println(inorderTraversal(root)) // 출력: [1 3 2]
}

 

방식

1. DFS 방식으로 왼쪽 서브트리 끝까지 탐색
   • 왼쪽 자식이 있으면 계속 재귀 호출
2. 더 이상 왼쪽 자식이 없으면 현재 노드를 방문
   • 현재 노드 값을 result 리스트에 저장
3. 오른쪽 서브트리 탐색
   • 오른쪽 자식이 있으면 다시 DFS로 탐색