이 진 트 리 의 각종 조작 총화

이 글 은 면접 에서 이 진 트 리 문 제 를 쉽게 해결 하 는 것 을 참고 하여 이 루어 집 니 다.

이 진 트 리 의 노드 개 수 를 구하 기

이 진 트 리 의 잎 노드 의 개 수 를 구하 세 요

이 진 트 리 의 깊이 구하 기

이 진 트 리 K 층 의 노드 개 수 를 구하 기

재 귀적 으로 전체 순서 중 순서 후 순서

비 재 귀적 으로 전체 순서 중 순서 후 순서 층 서 를 옮 겨 다 닌 다.

1 앞 순 서 를 옮 겨 다 닌 다

2 중 순서 옮 겨 다 니 기

3 후 순서 옮 겨 다 니 기

4 층 순서 옮 겨 다 니 기

이 진 트 리 를 질서 있 는 양 방향 링크 로 바 꿉 니 다

이 진 트 리 의 거울 구하 기

두 그루 의 이 진 트 리 가 구조 가 같 는 지 판단 한다

이 진 트 리 가 밸 런 스 이 진 트 리 인지 아 닌 지 판단 하기

이 진 트 리 가 이 진 트 리 검색 인지 판단

이 진 트 리 가 완전 이 진 트 리 인지 아 닌 지 판단 하기

이 진 트 리 중 두 노드 의 최저 공공 조상 노드

이 진 트 리 의 노드 최대 거리 구하 기

앞 순서 와 중간 순서 로 이 진 트 리 를 재 구축 합 니 다

모든 원본 코드:https://github.com/qzxin/BinaryTree/blob/master/binary-tree-all.cpp
1. 이 진 트 리 의 노드 갯 수 구하 기
재 귀 구 해, 이 진 트 리 의 노드 개 수 는 왼쪽 서브 트 리 의 개수 + 오른쪽 서브 트 리 의 개수 + 1 (뿌리) 과 같 습 니 다.

//          
int GetNums(BinaryTreeNode* root) {
    if (root == NULL)
        return 0;
    return GetNums(root->m_pLeft) + GetNums(root->m_pRight) + 1;
}

이 진 트 리 의 잎 노드 의 개 수 를 구하 다.
잎 노드 의 정 의 는 자신 이 비어 있 지 않 고 좌우 가 NULL 입 니 다.이 진 트 리 의 노드 개 수 를 구 하 는 것 과 유사 합 니 다. 좌우 가 NULL 이 어야 만 1 개 입 니 다.

int GetLeafNodeNums(BinaryTreeNode* root) {
    if (root == NULL)
        return 0;
    if (root->m_pLeft == NULL && root->m_pRight == NULL)
        return 1;
    int leftNums = GetLeafNodeNums(root->m_pLeft);
    int rightNums = GetLeafNodeNums(root->m_pRight);
    return leftNums+rightNums;
}

2. 이 진 트 리 깊이 구하 기
재 귀 구 해, 이 진 트 리 의 깊이 는 좌우 서브 트 리 깊이 의 최대 치 + 1 (뿌리) 과 같 습 니 다.

//        
int GetDepth(BinaryTreeNode* root) {
    if (root == NULL)
        return 0;
    return max(GetDepth(root->m_pLeft), GetDepth(root->m_pRight)) + 1;
}

3. 이 진 트 리 K 층 노드 개수 구하 기
귀속 실현 k = 1, nums = 1;이 진 트 리 K 층 의 노드 개수 = 왼쪽 트 리 K - 1 층 의 노드 개수 + 오른쪽 트 리 K - 1 층 의 노드 개수

//      K      
int GetNLevelNums(BinaryTreeNode* root, int k) {
    if (root == NULL || k == 0)
        return 0;
    if (k == 1)
        return 1;
    //     k-1      
    return GetNLevelNums(root->m_pLeft, k-1) + GetNLevelNums(root->m_pRight, k-1);
}

4. 재 귀적: 앞 순서, 가운데 순서, 뒤 순서

//     ：    ，    ，    
void visit(BinaryTreeNode* root) {
    cout << root->m_val << " ";
}
void PreOrderTravel(BinaryTreeNode* root) {
    if (root == NULL)
        return;
    visit(root);
    PreOrderTravel(root->m_pLeft);
    PreOrderTravel(root->m_pRight);
}
void InOrderTravel(BinaryTreeNode* root) {
    if (root == NULL)
        return;
    InOrderTravel(root->m_pLeft);
    visit(root);
    InOrderTravel(root->m_pRight);
}
void PostOrderTravel(BinaryTreeNode* root) {
    if (root == NULL)
        return;
    PostOrderTravel(root->m_pLeft);
    PostOrderTravel(root->m_pRight);
    visit(root);

}

5. 비 재 귀적 옮 겨 다 니 기: 앞 순서, 중간 순서, 뒤 순서, 층 순서
5.1 앞 순서 옮 겨 다 니 기
먼저 뿌리 에 접근 한 다음 에 오른쪽 노드 를 누 르 고 왼쪽 노드 는 창고 에 들어간다.(방문 시 순 서 는 뿌리, 왼쪽, 오른쪽)

void PreOrderTravel(BinaryTreeNode* root) {
    if (root == NULL)
        return;
    stack s;
    s.push(root);
    while (s.empty() == false) {
        root = s.top();
        visit(root);
        s.pop();
        if (root->m_pRight)
            s.push(root->m_pRight);
        if (root->m_pLeft)
            s.push(root->m_pLeft);
    }
}

5. 2 중 순 옮 겨 다 니 기
먼저 창고 에 들 어간 후에 방문 하 다.중간 순 서 는 먼저 왼쪽 노드 를 방문 해 야 하기 때문에 나무의 마지막 왼쪽 노드 를 눌 러 야 접근 할 수 있 습 니 다.마지막 왼쪽 노드 에 왼쪽 노드 (뿌리 에 해당) 가 없 으 면 오른쪽 트 리 를 옮 겨 다 니 기 시작 합 니 다.

void InOrderTravelRecur(BinaryTreeNode* root) {
    if (root == NULL)
        return;
    stack s;
    BinaryTreeNode* node  = root;
    while (node != NULL || s.empty() == false) {
        if (node) {
            s.push(node);
            node = node->m_pLeft;
        } else {
            node = s.top();
            s.pop();
            visit(node);
            node = node->m_pRight;
        }
    }
}

5.3 후 순 옮 겨 다 니 기
2 개의 창고 로 실현,

//    s1：  ，  ，  ； 
//  s2：     ，  ，  ；(      ： ， ， )
void PostOrderTravelRecur(BinaryTreeNode* root) {
    if (root == NULL)
        return;
    stack s1;
    stack s2;
    BinaryTreeNode* node = root;
    s1.push(node);
    while (s1.empty() == false) {
        node = s1.top();
        s1.pop();
        s2.push(node); //   s2
        if (node->m_pLeft)
            s1.push(node->m_pLeft);//      s1
        if (node->m_pRight)
            s1.push(node->m_pRight); //      s1
    }
    while (s2.empty() == false) {
        node = s2.top();
        s2.pop();
        visit(node);
    }
}

5.4 층 차 옮 겨 다 니 기
한 층 한 층 방문, 먼저 들 어가 고 먼저 나 가 며 대기 열 을 사용 하여 이 루어 집 니 다.루트 에 접근 한 후 왼쪽, 오른쪽으로 대기 열 에 들 어 갑 니 다.

void LevelOrderTravel(BinaryTreeNode* root) {
    if (root == NULL)
        return;
    queue q;
    q.push(root);
    while (q.empty() == false) {
        root = q.front();
        visit(root);
        q.pop();
        if (root->m_pLeft)
            q.push(root->m_pLeft);
        if (root->m_pRight)
            q.push(root->m_pRight);
    }
}

6. 이 진 트 리 를 질서 있 는 양 방향 링크 로 바 꿉 니 다.
순환 실현, 이 진 트 리 는 왼쪽 나무, 뿌리, 오른쪽 나무 로 나 눌 수 있 습 니 다. 양 방향 링크 의 머리 끝 은 pFirst, pLast 입 니 다.

뿌리 가 비어 있 음: pFirst, pLast 는 NULL

왼쪽 나무 처리

왼쪽 나무 가 비어 있 으 면 뿌리 는 양 방향 링크 의 머리

이다.

왼쪽 나무 가 비어 있 지 않 습 니 다. 왼쪽 나무 양 방향 링크 의 머리 는 최종 양 방향 링크 의 머리 입 니 다.왼쪽 나무 양 방향 링크 의 꼬리 와 뿌리 가 연결 되 어 있 습 니 다.

오른쪽 나무 처리

오른쪽 나무 공: 뿌리 는 양 방향 링크 의 꼬리 부분

오른쪽 나무 가 비어 있 지 않 습 니 다. 오른쪽 나무 양 방향 링크 의 꼬리 는 최종 양 방향 링크 의 꼬리 입 니 다.오른쪽 나무 양 방향 링크 의 머리 와 뿌리 가 연결 되 어 있 습 니 다.

따라서 최종 양 방향 링크 의 머리 와 꼬리 를 밝 히 는 것 외 에 왼쪽, 오른쪽 트 리 가 양 방향 링크 의 머리 와 꼬리 로 바 뀌 었 다 고 밝 혔 다.

//                
void CovertToList(BinaryTreeNode* root, BinaryTreeNode* &pFirst, BinaryTreeNode* &pLast) {
    BinaryTreeNode* pLeftFirst(NULL), *pLeftLast(NULL), *pRightFirst(NULL), *pRightLast(NULL);
    if (root == NULL) {
        pFirst = NULL;
        pLast = NULL;
        return;
    }

    if (root->m_pLeft == NULL) {
        pFirst = root;
    } else {
        CovertToList(root->m_pLeft, pLeftFirst, pLeftLast);
        pLeftLast->m_pRight = root; 
        root->m_pLeft = pLeftLast;
        pFirst = pLeftFirst;
    }

    if (root->m_pRight == NULL) {
        pLast = root;
    } else {
        CovertToList(root->m_pRight, pRightFirst, pRightLast);
        pRightFirst->m_pLeft = root;
        root->m_pRight = pRightFirst;
        pLast = pRightFirst;
    }

}

7. 이 진 트 리 의 거울 을 구하 라
재 귀 하 는 교환 나무의 좌우 나무.

//        
BinaryTreeNode* MirrorTree(BinaryTreeNode* root) {
    if (root == NULL)
        return NULL;
    BinaryTreeNode* pLeft = MirrorTree(root->m_pLeft);
    BinaryTreeNode* pRight = MirrorTree(root->m_pRight);
    root->m_pLeft = pRight;
    root->m_pRight = pLeft;
    return root;
}

8. 이 진 트 리 두 그루 의 구조 가 동일 한 지 판단
재 귀 실현: 먼저 뿌리 가 같은 지 판단 한 다음 에 왼쪽 나무 와 오른쪽 나무 가 같은 지 판단 합 니 다 / / 두 그루 의 이 진 트 리 가 구조 가 같은 지 판단 합 니 다.

bool TreeStructCmp(BinaryTreeNode* root1, BinaryTreeNode* root2) {
    if (root1 == NULL && root2 == NULL)
        return true;
    if (root1 != root2)
        return false;
    bool leftResult = TreeStructCmp(root1->m_pLeft, root2->m_pLeft);
    bool rightResult = TreeStructCmp(root1->m_pRight, root2->m_pRight);
    return leftResult && rightResult;
}

9. 이 진 트 리 가 밸 런 스 이 진 트 리 인지 판단
모든 나무 가 균형 트 리 여야 균형 트 리 라 는 것 을 보증 할 수 있다.따라서 좌우 나무 가 균형 이 맞 는 지 판단 하고 좌우 나무의 깊이 를 기록 한 뒤 나무의 균형 여 부 를 판단 한다.

bool IsAVL(BinaryTreeNode* root) {
    int depth;
    return IsAVLTree(root, depth);
}
//     ，   1   
bool IsAVLTree(BinaryTreeNode* root, int &depth) {
    if (root == NULL) {
        depth = 0;
        return true;
    } 
    int leftDepth, rightDepth;
    //     ，             ，        
    if (IsAVLTree(root->m_pLeft, leftDepth) && IsAVLTree(root->m_pRight, rightDepth)) {
        if (abs(leftDepth-rightDepth) <= 1) {
            depth = max(leftDepth, rightDepth)+1;
            return true;
        }
    }
    return false;
}

10. 이 진 트 리 가 이 진 트 리 검색 인지 판단
주의: 왼쪽 노드 < = 뿌리 < = 오른쪽 노드 만 비교 하면 이것 은 이 진 트 리 를 검색 하 는 것 이 라 고 판단 할 수 없습니다. 이것 은 오른쪽 트 리 의 모든 노드 값 이 왼쪽 트 리 의 모든 노드 보다 크다 는 것 을 보장 할 수 없 기 때 문 입 니 다.아래 그림 에서 보 듯 이 그것 은 BST 가 아니다.

    4
1       5
     0     6

중간 순 서 를 통 해 이 진 트 리 를 검색 하 는 지 여 부 를 판단 합 니 다.

//              
bool IsBST(BinaryTreeNode* root) {
    int prev = INT_MIN; //     ，    
    return IsBSTreeHelper(root, prev);
}
//     ，             
bool IsBSTreeHelper(BinaryTreeNode* root, int &prev) {
    if (root == NULL)
        return true;
    if (IsBSTreeHelper(root->m_pLeft, prev)) {
        if (root->m_val >= prev) {
            prev = root->m_val;
            if (IsBSTreeHelper(root->m_pRight, prev))
                return true; //      、 、        
            else
                return false; //     
        } else {
            return false; //     
        }
    } else {
        return false; //     
    }
}

11. 이 진 트 리 가 완전 이 진 트 리 인지 아 닌 지 판단
완전 이 진 트 리 는 마지막 층 오른쪽 에 있어 야 빈 노드 가 존재 할 수 있 습 니 다.한 노드 에 빈 트 리 가 있 으 면 모든 노드 에 NULL 만 포함 되 어야 합 니 다.

빈 트 리 가 없 을 때 현재 노드 의 좌우 트 리 를 순서대로 대기 열 에 눌 러 줍 니 다

빈 트 리 가 있 을 때 현재 노드 와 대기 열 에 있 는 후속 노드 의 좌우 트 리 는 비어 있어 야 완전 이 진 트 리 입 니 다.

/              
//     ，            ，            NULL
bool IsCompleteBinaryTree(BinaryTreeNode* root) {
    if (root == NULL)
        return true;
    queue<BinaryTreeNode* > q;
    bool HaveNULL = false;
    q.push(root);
    while (q.empty() == false) {
        root = q.front();
        q.pop();
        if (HaveNULL) {
            if (root->m_pLeft || root->m_pRight)
                return false;
        } else {
            if (root->m_pLeft && root->m_pRight) {
                //     
                q.push(root->m_pLeft);
                q.push(root->m_pRight);
            } else if (root->m_pLeft && root->m_pRight == NULL) {
                //    ，  
                HaveNULL = true;
                q.push(root->m_pLeft);
            } else if (root->m_pLeft == NULL && root->m_pRight) {
                //   ，   
                return false;
            } else {
                //     
                HaveNULL = true;
            }
        }
    }
    return true;
}

12. 이 진 트 리 에서 두 노드 의 최저 공공 조상 노드 를 구한다.
재 귀 해법: (1) 만약 에 두 노드, 하 나 는 왼쪽 나무 에 있 고 하 나 는 오른쪽 나무 에 있 으 면 가장 낮은 공공 조상 노드 는 뿌리 (2) 이다. 만약 에 두 노드 가 모두 왼쪽 나무 에 있 으 면 재 귀 하여 왼쪽 나 무 를 처리한다.반대로 오른쪽 하위 트 리 처리
트 리 에서 node 1 을 찾 고 경 로 를 저장 합 니 다. node 1 을 찾 지 못 하면 경로 의 노드 pop 을 되 돌려 줍 니 다.트 리 에서 node 2 를 찾 고 경 로 를 저장 합 니 다. node 1 을 찾 지 못 하면 경로 의 노드 pop 을 되 돌려 줍 니 다.1 개 를 찾 지 못 하면 NULL 로 돌아 가 고, 다 찾 으 면 2 개의 경 로 를 시작 으로 뒤로 옮 겨 다 니 며 마지막 공 통 된 노드 를 찾 습 니 다.

//                   
BinaryTreeNode* GetLastCommonParent(BinaryTreeNode* root, BinaryTreeNode* node1, BinaryTreeNode* node2) {
    if (root == NULL || node1 == NULL || node2 == NULL)
        return NULL;
    list path1, path2;
    bool found1 = GetPath(root, node1, path1);
    bool found2 = GetPath(root, node2, path2);
    BinaryTreeNode* pLast = NULL;
    if (!found1 || !found2)
        return NULL;
    //              
    list::const_iterator iter1 = path1.begin();
    list::const_iterator iter2 = path2.begin();
    while (iter1 != path1.end() && iter2 != path2.end()) {
        if (*iter1 != *iter2)
            break;
        pLast = *iter1;
        iter1++;
        iter2++;
    }
    return pLast;
}
//           
bool GetPath(BinaryTreeNode* root, BinaryTreeNode* node, list &path) {
    if (root == node) {
        path.push_back(root);
        return true;
    }
    if (root == NULL)
        return false;
    bool found = false;
    path.push_back(root); //       
    found = GetPath(root->m_pLeft, node, path); //      
    if (!found)
        found = GetPath(root->m_pRight, node, path); //       
    if (!found)
        path.pop_back(); //        ，pop            
    return found;
}

13. 이 진 트 리 의 노드 최대 거리 구하 기
이 진 트 리 에서 노드 의 최대 거리 max Distance 는 두 노드 가 연 결 된 경로 길이 의 최대 치 를 말 합 니 다.

나 무 는 비어 있 고 거 리 는 0 이다.

나무 가 비어 있 지 않 습 니 다. 최대 거 리 는 3 가지 가능성 이 있 습 니 다. 왼쪽 나무 에서 최대 거리, 오른쪽 나무 에서 최대 거리, 왼쪽 나무 에서 뿌리 까지 그리고 오른쪽 나무 까지 의 최대 거리

int GetMaxDistance(BinaryTreeNode* root) {
    int maxLeft = 0, maxRight = 0; //            
    return GetMaxDistRecur(root, maxLeft, maxRight); //         ，             
}

//maxLeft, maxRight                
int GetMaxDistRecur(BinaryTreeNode* root, int &maxLeft, int &maxRight) {
    if (root == NULL) {
        maxLeft = 0, maxRight = 0;
        return 0;
    }
    int maxLL, maxLR, maxRL, maxRR;
    int maxDistLeft, maxDistRight; //  、         
    if (root->m_pLeft) {
        maxDistLeft = GetMaxDistRecur(root->m_pLeft, maxLL, maxLR);
        maxLeft = max(maxLL, maxRR) + 1;
    } else {
        maxDistLeft = 0;
        maxLeft = 0;
    }
    if (root->m_pRight) {
        maxDistRight = GetMaxDistRecur(root->m_pRight, maxRL, maxRR);
        maxRight = max(maxRL, maxRR) + 1;
    } else {
        maxDistRight = 0;
        maxRight = 0;
    }
    return max(maxLeft+maxRight, max(maxDistLeft, maxDistRight));
}

14. 앞 순서 와 중간 순서 로 두 갈래 나 무 를 재 구축 합 니 다.
앞 순 서 는 뿌리 이다.중 서 의 한 노드 의 왼쪽 은 왼쪽 나무 이 고 오른쪽 은 오른쪽 나무 이다.따라서 이전 순서 에서 1 개의 뿌리 를 확정 한 다음 에 중간 순서 에서 이 뿌리 를 찾 아 이 뿌리 에 속 하 는 좌우 나무 범 위 를 확인한다.좌우 자 수 를 재 귀적 으로 처리 하 다.

//                    
BinaryTreeNode* RebuildBinaryTree(int* preorder, int* inorder, int nums) {
    if (preorder == NULL || inorder == NULL || nums <= 0)
        return NULL;
    BinaryTreeNode* root = new BinaryTreeNode(preorder[0]); //  
    int rootPositionOnInorder = -1;
    for (int i = 0; i < nums; i++) {
        if (inorder[i] == root->m_val) {
            rootPositionOnInorder = i; //       
            break;
        }
    }
    if (rootPositionOnInorder == -1) {
        cout << "Input Error." << endl;
    }
    // Rebuild Left Tree
    root->m_pLeft = RebuildBinaryTree(preorder+1, inorder, rootPositionOnInorder);
    // Rebuild Right Tree
    root->m_pRight = RebuildBinaryTree(preorder+1+rootPositionOnInorder, inorder+1+rootPositionOnInorder, nums-rootPositionOnInorder-1);
    return root;
}