JavaScript로 이진트리 뒤집기

LeetCode 226. Invert Binary Tree

문제링크

문제분석

이진트리가 함수의 인자로 들어올 떄, 루트를 기준으로 왼쪽, 오른쪽 뒤집어진 이진트리를 리턴하기

이 문제에 대해 재밌는 사실 한가지가 있는데, Homebrew 를 개발한 개발자 Max Howell의 다음과 같은 트윗에서 영감을 받았다고 한다.

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.

돌파구

역시나, 이번에도 재귀를 통해서 문제를 해결할 수 있다.
이번에도, 재귀의 핵심은, 자식들에게 일을 위임하는 것. 바뀌어서 나한테 와 => dfs(node.left), dfs(node.right) 호출 이미 잘 바뀌어서 온 놈들의 자리를 바꾸어 주기만 하면 된다.

구현

• 재귀 호출이 끝나는 조건 : 들어온 노드가 null 이라면 null 을 리턴한다. 즉, 가장 밑단을 만난 것
• left = dfs(node.left), right = dfs(node.right) dfs 함수를 재귀로 호출해서, 뒤집어진 트리를 넘겨받는다.
• node.left = right, node.right = left 재귀가 끝나고 뒤집어진 트리에 대해서, 왼쪽 오른쪽을 뒤집어 준다.
• 리턴 : 왼쪽, 오른쪽이 뒤집어진 node 를 리턴한다.