검지 offer 나무 테마

나 무 는 가장 자주 사용 하 는 데이터 구조 중의 하나 이다.나무의 뿌리 결점 과 잎 결점 은 지침 으로 연결 되 기 때문에 대량의 지침 조작 과 관련 될 수 있다.
이 진 트 리 는 가장 흔히 볼 수 있 는 나무 로 가장 흔히 볼 수 있 는 것 은 옮 겨 다 니 는 작업 이다. 앞 순서, 중간 순서 와 뒤 순 서 는 모두 재 귀적 으로 실현 할 수 있다.일부 흔히 볼 수 있 는 이 진 트 리: a. 이 진 트 리 검색: 빈 나무 이거 나 왼쪽 노드 가 뿌리 노드 보다 작 거나 오른쪽 노드 가 뿌리 노드 보다 크다.
b. 더미: 일반적인 상황 에서 완전 이 진 트 리 로 최소 더미 와 최대 더미 로 나 뉘 는데 가장 많은 문 제 는 더미 로 최소 더 미 를 해결 할 수 있 습 니 다. 뿌리 노드 의 값 은 최소 최대 더미: 뿌리 노드 의 값 이 가장 큽 니 다.
이 진 트 리 는 동적 검색 을 실현 하기 위해 디자인 된 데이터 구조 로 검색 작업 을 위 한 것 입 니 다. 이 진 트 리 에서 노드 를 찾 는 평균 시간 복잡 도 는 O (log n) 입 니 다.더 미 는 정렬 을 실현 하기 위해 디자인 된 데이터 구조 로 검색 작업 을 위 한 것 이 아니 므 로 더 미 를 찾 을 때 노드 를 찾 으 려 면 옮 겨 다 녀 야 합 니 다. 평균 시간 복잡 도 는 O (n) 입 니 다.
c. 붉 은 검 은 나무 (이것 은 매우 복잡 하 다. 시간 이 있 으 면 천천히 연구 ~) 나무의 결점 은 빨간색, 검은색 두 가지 색깔 로 정의 하고 규칙 을 통 해 뿌리 결점 에서 잎 결점 까지 의 최 장 경로 의 길이 가 최 단 경로 의 두 배 를 초과 하지 않도록 확보한다.c + + 의 STL 에 서 는 set, map 등 이 모두 빨 간 검 은 나 무 를 기반 으로 이 루어 집 니 다.
(1) 이 진 트 리 의 결 점 수 를 구 하 는 사고: 전형 적 인 재 귀 이다.

int GetNodeNum(BinaryTreeNode *pRoot)
{
    if(pRoot == NULL)
        return 0;
    return GetNodeNum(pRoot->left)+GetNodeNum(pRoot->right)+1;
}

디 버 깅:

#include 

using namespace std;

struct BinaryTreeNode
{
    int val;
    BinaryTreeNode *left;
    BinaryTreeNode *right;
    BinaryTreeNode(int x):val(x),left(NULL),right(NULL){}
};

int GetNodeNum(BinaryTreeNode *pRoot)
{
    if(pRoot == NULL)
        return 0;
    return GetNodeNum(pRoot->left)+GetNodeNum(pRoot->right)+1;
}
int main()
{
    BinaryTreeNode proot = BinaryTreeNode(0);
    BinaryTreeNode leftnode = BinaryTreeNode(1);
    BinaryTreeNode rightnode = BinaryTreeNode(3);
    BinaryTreeNode rrightnode = BinaryTreeNode(3);
    proot.left = &leftnode;
    proot.right = &rightnode;
    rightnode.right = &rrightnode;

    int node_num = GetNodeNum(&proot);
    cout << node)num <0;
}

(2) 이 진 트 리 의 앞 순 서 를 입력 하고 중간 순 서 를 옮 겨 다 니 는 결 과 를 입력 하 십시오. 이 이 진 트 리 를 다시 만 드 십시오.입력 한 앞 순서 와 중간 순 서 를 옮 겨 다 니 는 결과 에 중복 되 는 숫자 가 없다 고 가정 합 니 다.예 를 들 어 앞 순서 옮 겨 다 니 기 시퀀스 {1, 2, 4, 7, 3, 5, 6, 8} 과 중간 순서 옮 겨 다 니 기 시퀀스 {4, 7, 2, 1, 5, 3, 8, 6} 을 입력 하면 이 진 트 리 를 다시 만 들 고 돌아 갑 니 다.사고: 앞 순 서 를 옮 겨 다 니 는 첫 번 째 값 은 바로 이 이 진 트 리 의 뿌리 결산 점 이기 때문에 중간 순 서 를 옮 겨 다 니 면서 이 값 을 찾 았 습 니 다. 왼쪽 은 왼쪽 나무 이 고 오른쪽 은 오른쪽 나무 입 니 다. 그래서 재 귀적 으로 해결 합 니 다.

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.size() == 0 || vin.size() == 0)
            return NULL;
        return ConstructCore(pre,vin);

    }
    TreeNode* ConstructCore(vector<int> &qianxu,vector<int> &zhongxu)
    {
        int RootValue = qianxu[0];
        //      
        TreeNode* newtree = new TreeNode(RootValue);
        newtree->left = NULL;
        newtree->right = NULL;

        vector<int> qianxuleftvec;
        vector<int> zhongxuleftvec;
        vector<int> qianxurightvec;
        vector<int> zhongxurightvec;
        int i = 0;
        int temp = 0;
        for (i =0;iif(RootValue != zhongxu[i])
            {
                zhongxuleftvec.push_back(zhongxu[i]);
                qianxuleftvec.push_back(qianxu[i+1]);
            }
            else
            {
                temp = i;
                break;
            }
        }
        for (i =temp+1;iif (qianxuleftvec.size()>0)    
            newtree->left = ConstructCore(qianxuleftvec,zhongxuleftvec);
        if (qianxurightvec.size()>0)    
            newtree->right = ConstructCore(qianxurightvec,zhongxurightvec);
        return newtree;
    }
};

(3) 두 그루 의 이 진 트 리 A, B 를 입력 하여 B 가 A 의 서브 구조 인지 아 닌 지 를 판단 한다.(ps: 빈 나 무 는 임의의 나무의 하위 구조 가 아니 라 고 약속 합 니 다)

class Solution {
public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        if(pRoot1 == NULL || pRoot2 == NULL)
            return false;
        return isSubtree(pRoot1, pRoot2) || HasSubtree(pRoot1->left,pRoot2) || HasSubtree(pRoot1->right,pRoot2);
    }
    bool isSubtree(TreeNode* pRootA, TreeNode* pRootB)
    {
        if (pRootB == NULL) return true;
        if (pRootA == NULL) return false;
        if (pRootB->val == pRootA->val)
            return isSubtree(pRootA->left, pRootB->left) && isSubtree(pRootA->right, pRootB->right);
        else return false;
    }
};

주어진 이 진 트 리 를 작 동 하여 원본 이 진 트 리 의 미 러 로 변환 합 니 다.입력 설명: 이 진 트 리 의 미 러 정의: 원본 이 진 트 리 8 / \ 6 10 / \ / \ 5 7 9 11 미 러 이 진 트 리 8 / \ 10 6 / \ / \ 11 9 7 5

class Solution {
public:
    void Mirror(TreeNode *pRoot) {
        if (pRoot == NULL)
            return;
        TreeNode *p=pRoot->left;
        pRoot->left=pRoot->right;
        pRoot->right=p;
        Mirror(pRoot->left);
        Mirror(pRoot->right);
    }
};