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

9581 단어
봄 이 불 러 와 서 직장 을 그만 두 고 집에 서 실습 일자 리 를 찾 으 려 고 한다.여러분 을 믿 습 니 다. 특히 대학 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 에서 나 왔 으 며 해당 제목 도 위 에서 찾 을 수 있다.그러나 그 동안 나 도 실습 일자 리 를 찾 았 고 몇 년 후에 벽돌 을 옮 기 러 갈 것 이다.찾 은 이상 춘 기 는 참여 하지 않 겠 습 니 다.

    좋은 웹페이지 즐겨찾기