Use DFS, referencing the property of a tree (i.e. child node is the root node of a subtree.)
- Visit the root node.
- If visited node is
nil, returnnil - Swap left and right nodes.
- Visit Swapped left and right nodes.
- Repeat Step 2 ~ 4.
- Time complexity:
$$O(n)$$
- Space complexity:
$$O(n)$$
func invertTree(root *TreeNode) *TreeNode {
if root == nil {
return nil
}
root.Left, root.Right = invertTree(root.Right), invertTree(root.Left)
return root
}Visit, But Use BFS. (for loop)
- Create Queue and push root node to it.
- If the queue is empty, return the
rootnode. - Otherwise, pop the top node.
- Swap the left and right children of the removed node.
- Push swapped children.
- Repeat Step
- Time complexity:
$$O(n)$$
- Space complexity:
$$O(n)$$
type Queue[T any] struct {
Index int
Nodes []T
}
func NewQueue[T any]() Queue[T] {
return Queue[T]{Nodes: make([]T, 0)}
}
func (q *Queue[T]) Push(node T) {
q.Nodes = append(q.Nodes, node)
}
func (q *Queue[T]) Pop() T {
ret := q.Nodes[q.Index]
q.Index++
return ret
}
func (q *Queue[T]) IsEmpty() bool {
return q.Index == len(q.Nodes)
}
func invertTree(root *TreeNode) *TreeNode {
q := NewQueue[*TreeNode]()
q.Push(root)
for !q.IsEmpty() {
t := q.Pop()
if t == nil {
continue
}
t.Left, t.Right = t.Right, t.Left
q.Push(t.Left)
q.Push(t.Right)
}
return root
}- 고언어에서
a, b = b, a처럼 간결한 코딩이 가능하다. - 포인터 타입과 일반 타입의 차이 (고언어에서는 일반 타입을 넘길 시 무조건 복사한다.)