트 리 - 인 버 트 바 이 너 리 트 리 (이 진 트 리 뒤 집기)
719 단어 데이터 구조 와 알고리즘 축적
Invert a binary tree.
4
/ \
2 7
/ \ / \
1 3 6 9
to
특히 이 한 마디:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.
생각:
데이터 구조의 기초 지식 을 복습 하고 이 진 트 리: 노드 개수 = 2 ^ n - 1 (n 은 나무의 깊이), 완전 이 진 트 리: 노드 개수 가 가장 많 음 = 2 ^ n - 1 (n 은 나무의 깊이), 노드 개수 가 가장 적 음 = 2 ^ (n 은 나무의 깊이) - 1) (n 은 나무의 깊이) 입 니 다. 따라서 완전 이 진 트 리 의 평균 깊이 는 logN (n 은 나무의 깊이) 입 니 다. 삭제 와 같은 작업 의 평균 시간 은 O (logN) 입 니 다.
이 문 제 는 각 노드 의 하위 나 무 를 위 치 를 바 꾸 고 오른쪽 은 왼쪽, 왼쪽 은 오른쪽 으로 바 꾸 는 것 이 가장 좋다 는 뜻 이다.
코드 (java):
4
/ \
7 2
/ \ / \
9 6 3 1