앉 아 라, 이것들 은 모두 이 진 트 리 의 기본 조작 이다!
흔히 볼 수 있 는 이 진 트 리 구현 코드
이전에 관련 글 을 쓴 적 이 있 는데, 이 진 트 리 를 어떻게 만 들 고 옮 겨 다 니 는 지 에 관 한 것 이 며, 여 기 는 더 이상 군말 하지 않 습 니 다.관심 있 는 동료 들 에 게 링크 를 제공 합 니 다. 이 점프 를 누 르 십시오.
이 진 트 리 뒤 집기
이 진 트 리 한 그루 에 대해 왼쪽 과 오른쪽 나 무 를 뒤 집 습 니 다. 다음 그림 과 같 습 니 다.
다음은 구체 적 인 실현 방향 을 분석한다.
빈 자 수 를 위 한 특수 처리 가 아 닙 니 다.
분석 과정
사실 이렇게 해서 우 리 는 이 진 트 리 가 어떻게 뒤 집 혔 는 지 모른다. 우 리 는 첫 번 째 그림 의 이 진 트 리 를 예 로 들 어 뒤 집 는 구체 적 인 과정 을 볼 수 있다.
2. 뿌리 결산 점 의 왼쪽 나 무 를 왼쪽 나무의 뿌리 결산 점 으로 삼 아 현재 뿌리 결산 점 을 빈 것 으로 처리 하고 빈 것 이 아 닐 때 좌우 자 나 무 를 교환 합 니 다.
3. 뿌리 가 맺 힌 오른쪽 나 무 를 오른쪽 나무의 뿌리 결산 점 으로 삼 아 현재 뿌리 결산 점 을 빈 것 으로 처리 하고 빈 것 이 아 닐 때 좌우 나 무 를 교환 합 니 다.
4. 반복 절차
2、
3. 마지막 으로 이 진 트 리 가 원래 의 미 러 구조 로 바 뀌 었 고 그 결 과 는 글 의 첫 번 째 설명도 참조 할 수 있 습 니 다.
예제 코드
위의 추리 과정 에 근거 하여 우 리 는 다음 과 같은 코드 를 얻 을 수 있다.
function reverseTree(root){
if( root !== null){
[root.left, root.right] = [root.right, root.left]
reverseTree(root.left)
reverseTree(root.right)
}
}
추리 과정 이 복잡 하지만 코드 를 자세히 살 펴 보면 옮 겨 다 니 는 코드 와 큰 차이 가 없 는 것 같 습 니 다. 출력 노드 를 교환 노드 로 만 들 었 을 뿐 입 니 다.
이 진 트 리 의 완전 대칭 여 부 를 판단 하 다.
좌우 가 완전히 대칭 되 는 이 진 트 리 는 이렇다. 그렇다면 어떻게 판단 할 것 인가?
우리 의 정상 적 인 사고 에 따라 대칭 여 부 를 보고 먼저 왼쪽 을 본 다음 에 오른쪽 을 보고 마지막 에 좌우 가 같 는 지 비교 합 니 다.이 동시에 우 리 는 이 진 트 리 의 깊이 가 비교적 클 때 우 리 는 좌우 만 비교 하 는 것 으로 는 부족 하 다 는 것 을 알 게 되 었 다.관찰 할 수 있 듯 이 우 리 는 좌 우 를 비교 한 후에 좌 우 와 우 우 우 를 비교 하고 좌 우 와 우 를 비교 해 야 한다.
분석 과정
이렇게 보면 비교적 복잡 하 다. 다음 에 우 리 는 그림 분석 을 살 펴 보 자.
function isSymmetrical(pRoot)
{
// write code here
if(!pRoot){
return true
}
return funC(pRoot.left, pRoot.right)
}
function funC(left, right){
if(!left){
return right === null
}
if(!right){
return false
}
if(left.val !== right.val){
return false
}
return funC(left.right, right.left) && funC(left.left, right.right)
}
두 갈래 나무의 깊이 를 구하 다
분석 과정
예제 코드
function deep(root){
if(!root){
return 0
}
let left = deep(root.left)
let right = deep(root.right)
return left > right ? left + 1 : right + 1
}
이 진 트 리 너비 구하 기
이 진 트 리 의 너 비 는 무엇 입 니까?나 는 그것 을 가장 많은 결점 수 를 가 진 층 에 포 함 된 결점 수로 이해한다. 예 를 들 어 아래 그림 에서 보 여 준 이 진 트 리 는 사실 그 폭 은 4 이다.
분석 과정
위의 그림 에 근거 하여 우 리 는 어떻게 이 진 트 리 의 너 비 를 계산 합 니까?사실 아주 간단 한 생각 이 있 습 니 다.
분석 과정 에 따라 우 리 는 대기 열 이라는 데이터 구 조 를 이용 하여 이 알고리즘 을 실현 할 수 있 습 니 다. 코드 는 다음 과 같 습 니 다.
function width(root){
if(!root){
return 0
}
let queue = [root], max = 1, deep = 1
while(queue.length){
while(deep--){
let temp = queue.shift()
if(temp.left){
queue.push(temp.left)
}
if(temp.right){
queue.push(temp.right)
}
}
deep = queue.length
max = max > deep ? max : deep
}
return max
}
이 진 트 리 재건
흔 하 다
제목 설명
앞 순 서 를 옮 겨 다 니 며 생 긴 시퀀스 와 중간 순 서 를 옮 겨 다 니 며 생 긴 시퀀스 에 따라 이 진 트 리 를 생 성 합 니 다.
사고 분석.
만약 이런 두 갈래 나무 가 있다 면:
알 수 있어 요.
이전 순 서 는 다음 과 같 습 니 다.
8 6 5 7 10 9 11,
중간 순 서 는 다음 과 같 습 니 다.
5, 6, 7, 8, 9, 10, 11 중 뚜렷 한 특징 이 있 는데 뿌리 결점 의 값 은
앞 순 서 는 서열 의 첫 번 째 값 을 옮 겨 다 니 며, 우 리 는...
중 서 를 옮 겨 다 니 는 서열 에서 쉽게 알 수 있 듯 이 뿌리 결점 좌우 양쪽 의 결점 은 각각 구성 된다.
왼쪽 나무 와
오른쪽 나무의 결점 이기 때문에 우 리 는 문 제 를 해결 하 는 방향 을 얻 을 수 있다.
function reConstructBinaryTree(pre, vin)
{
if(!pre || !vin || !pre.length || !vin.length){
return null
}
let root = new TreeNode(pre[0]),
tIndex = vin.indexOf(pre[0]),
leftIn = [],leftPre = [],rightIn = [],rightPre = []
for(let i = 0; i < tIndex; i++){
leftIn.push(vin[i])
leftPre.push(pre[i+1])
}
for(let i = tIndex+1; i < pre.length; i++){
rightIn.push(vin[i])
rightPre.push(pre[i])
}
//
root.left = reConstructBinaryTree(leftPre, leftIn)
root.right = reConstructBinaryTree(rightPre, rightIn)
return root
}
이상 의 사고, 코드 에 오류 가 있 으 면 댓 글 에서 지적 해 주 십시오!
총결산
코드 부분 은 우 객 망 인 검 지 offer 에서 나 왔 으 며 해당 제목 도 위 에서 찾 을 수 있다.그러나 그 동안 나 도 실습 일자 리 를 찾 았 고 몇 년 후에 벽돌 을 옮 기 러 갈 것 이다.찾 은 이상 춘 기 는 참여 하지 않 겠 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.