앉 아 라, 이것들 은 모두 이 진 트 리 의 기본 조작 이다!

봄 이 불 러 와 서 직장 을 그만 두 고 집에 서 실습 일자 리 를 찾 으 려 고 한다.여러분 을 믿 습 니 다. 특히 대학 3 학년, 4 학년 학생 들 은 모두 채용 요구 에서 이런 요 구 를 자주 볼 수 있 습 니 다. 흔히 볼 수 있 는 데이터 구조 와 알고리즘 을 잘 알 고 있 습 니 다.흔히 볼 수 있 는 데이터 구 조 는 링크, 이 진 트 리 가 있 는데 더 높 은 것 을 요구 하면 빨 간 검 은 나무, AVL 트 리 와 같은 고급 데이터 구 조 를 실현 할 수 있 습 니 다.이 를 통 해 알 수 있 듯 이 데이터 구조 와 알고리즘 은 비교적 중요 하고 최근 에 도 이 분야 의 지식 을 복습 하고 있다.이 편 은 복습 과정 에서 만 났 던 총 결 을 위해 저 와 같이 면접 을 준비 하 는 학생 들 에 게 참고 도 해 드 립 니 다.또한 편폭 이 제한 되 어 있 기 때문에 본 편의 중점 은 이 진 트 리 의 흔 한 알고리즘 과 실현 에 있다.
흔히 볼 수 있 는 이 진 트 리 구현 코드
이전에 관련 글 을 쓴 적 이 있 는데, 이 진 트 리 를 어떻게 만 들 고 옮 겨 다 니 는 지 에 관 한 것 이 며, 여 기 는 더 이상 군말 하지 않 습 니 다.관심 있 는 동료 들 에 게 링크 를 제공 합 니 다. 이 점프 를 누 르 십시오.
이 진 트 리 뒤 집기
이 진 트 리 한 그루 에 대해 왼쪽 과 오른쪽 나 무 를 뒤 집 습 니 다. 다음 그림 과 같 습 니 다.
다음은 구체 적 인 실현 방향 을 분석한다.

뿌리 결점 이 비어 있 는 상황 에 대해 서 는 제외 해 야 합 니 다. null 은 하나의 대상 이 아니 기 때문에 좌우 나무 가 존재 하지 않 고 뒤 집 을 수 있 는 상황

한 그루 의 결점 만 있 는 이 진 트 리 emmm 에 대해 서도 뒤 집 을 수 있 습 니 다. 이때 뿌리 결산 점 의 좌우 자 나 무 는 null 이 고 좌우 자 나 무 를 교환 하 는 것 은 사실은 두 개의 null 을 교환 하 는 것 입 니 다. 이론 적 으로 뒤 집 혔 지만 사실은 우리 가 본 것 과 뒤 집 히 지 않 은 결 과 는 똑 같 습 니 다

.

두 개 또는 두 개 이상 의 결점 을 가 진 이 진 나무 에 대해 이 진 나 무 는 다음 과 같은 그림 으로 표시 할 수 있다.

왼쪽 나무 나 오른쪽 나무 만 뒤 집 을 수 있 음 을 알 수 있다.이 말 은 빈 자 수 를 위해 빈 자 수 를 교환 할 수 있다 는 것 과 같다. 즉,
빈 자 수 를 위 한 특수 처리 가 아 닙 니 다.
분석 과정
사실 이렇게 해서 우 리 는 이 진 트 리 가 어떻게 뒤 집 혔 는 지 모른다. 우 리 는 첫 번 째 그림 의 이 진 트 리 를 예 로 들 어 뒤 집 는 구체 적 인 과정 을 볼 수 있다.

먼저 우 리 는 뿌리 결점 에 대해 공 처 리 를 해 야 한다. 뿌리 결점 이 비어 있 지 않 은 상황 에서 좌우 나무 (좌우 나무 가 비어 있어 도) 가 존재 한 다음 에 좌우 자 나 무 를 교환 해 야 한다.

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)
    }
}

추리 과정 이 복잡 하지만 코드 를 자세히 살 펴 보면 옮 겨 다 니 는 코드 와 큰 차이 가 없 는 것 같 습 니 다. 출력 노드 를 교환 노드 로 만 들 었 을 뿐 입 니 다.
이 진 트 리 의 완전 대칭 여 부 를 판단 하 다.
좌우 가 완전히 대칭 되 는 이 진 트 리 는 이렇다. 그렇다면 어떻게 판단 할 것 인가?

뿌리 결점 이 비어 있 을 때 이 때 는 빈 이 진 트 리 로 대칭 조건 (- - |)

을 만족시킨다.

한 개의 결점 만 있 을 때 좌우 자 수 는 모두 null 로 좌우 대칭 조건

을 만족시킨다.

두 개의 결점 만 있 을 때 이때 좌우 자 수 는 반드시 하나 가 비어 대칭 적 인 상황 이 존재 할 수 없다

.

결산 포인트 가 세 개 와 세 개 이상 일 때 이 진 트 리 는 대칭 적 인 가능성 이 있다.

우리 의 정상 적 인 사고 에 따라 대칭 여 부 를 보고 먼저 왼쪽 을 본 다음 에 오른쪽 을 보고 마지막 에 좌우 가 같 는 지 비교 합 니 다.이 동시에 우 리 는 이 진 트 리 의 깊이 가 비교적 클 때 우 리 는 좌우 만 비교 하 는 것 으로 는 부족 하 다 는 것 을 알 게 되 었 다.관찰 할 수 있 듯 이 우 리 는 좌 우 를 비교 한 후에 좌 우 와 우 우 우 를 비교 하고 좌 우 와 우 를 비교 해 야 한다.
분석 과정
이렇게 보면 비교적 복잡 하 다. 다음 에 우 리 는 그림 분석 을 살 펴 보 자.

뿌리 결점 정도 의 아 이 를 비교 해 보 자

왼쪽 뿌리 결산 점 의 왼쪽 아이 와 오른쪽 뿌리 결산 점 의 오른쪽 아 이 를 비교

왼쪽 뿌리 결산 점 의 오른쪽 아이 와 오른쪽 뿌리 결산 점 의 왼쪽 아 이 를 비교

이상 과정 반복...

예제 코드

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)
}

두 갈래 나무의 깊이 를 구하 다
분석 과정

뿌리 결점 이 하나 밖 에 없 을 때 이 진 트 리 의 깊이 는 1

이다.

왼쪽 나무 만 있 을 때 이 진 트 리 의 깊이 는 왼쪽 나무 깊이 에 1

을 더 합 니 다.

오른쪽 나무 만 있 을 때 이 진 트 리 깊이 는 오른쪽 나무 깊이 1

좌우 나무 가 동시에 존재 할 때 이 진 트 리 의 깊이 는 좌우 나무 중 깊이 가 가장 큰 자 에 게 1

을 더 합 니 다.
예제 코드

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 이다.
분석 과정
위의 그림 에 근거 하여 우 리 는 어떻게 이 진 트 리 의 너 비 를 계산 합 니까?사실 아주 간단 한 생각 이 있 습 니 다.

1 층 의 결산 점 수 를 계산 하여 보존

2 층 의 결 점 수 를 계산 하여 1, 2 층 에서 비교적 큰 결 점 수 를 보존 합 니 다

.

상기 과정 반복

예제 코드
분석 과정 에 따라 우 리 는 대기 열 이라는 데이터 구 조 를 이용 하여 이 알고리즘 을 실현 할 수 있 습 니 다. 코드 는 다음 과 같 습 니 다.

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 에서 나 왔 으 며 해당 제목 도 위 에서 찾 을 수 있다.그러나 그 동안 나 도 실습 일자 리 를 찾 았 고 몇 년 후에 벽돌 을 옮 기 러 갈 것 이다.찾 은 이상 춘 기 는 참여 하지 않 겠 습 니 다.