두 갈래 나무 더미 2019-04-17

두 갈래 나무

두 갈래 검색 트리를 실현하고 삽입, 삭제, 검색 작업을 지원합니다

두 갈래 찾기 트리의 어떤 노드의 후계, 선구 노드를 찾습니다

두 갈래 나무의 앞, 중, 뒤 순서와 층별로 훑어보는 것을 실현한다

그리고 leetcode의 검증 2차원 검색 트리(98)와 2차원 트리 차원 반복(102107)을 완성합니다!(선택)(지난 4일차 퀘스트 보류)주: 이것은 아래의 연습 문제와 중복됩니다**

쌓다

작은 덤프, 큰 덤프, 우선순위 대기열을 실현한다

무더기 정렬을 실현한다

우선순위 대기열을 이용하여 K 개의 질서수 그룹을 합친다

동적 데이터 집합의 최대 Top K를 구한다

셋째 날 정렬 학습(복습)

그에 맞는 Leet Code 연습 문제.
1. Invert Binary Tree(이차 트리 뒤집기)
영문:https://leetcode.com/problems/invert-binary-tree/
중국어 버전:https://leetcode-cn.com/problems/invert-binary-tree/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
// 
class Solution {    // 
public:
    TreeNode* invertTree(TreeNode* root) {
        
        if (root == NULL)
            return NULL;
        
        TreeNode *pro = root->left;
        root->left = invertTree(root->right);
        root->right = invertTree(pro);
        return root;        
    }
};

// 
class Solution {    //   
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return NULL;
        queue q;     // q
        q.push(root);           // root 
        while (!q.empty()) {    
            TreeNode *node = q.front(); //   q.back  q.size 
            q.pop();            //q.pop()  ， ；
            TreeNode *tmp = node->left;
            node->left = node->right;
            node->right = tmp;
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        return root;       
    }
};

2. Maximum Depth of Binary Tree(이차 트리의 최대 깊이)
영문:https://leetcode.com/problems/maximum-depth-of-binary-tree/
중국어 버전:https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == NULL)
            return 0;
        if(root->left == NULL && root->right == NULL)
            return 1;
        int left = maxDepth(root->left) + 1;    // ，misDepth 
        int right = maxDepth(root->right) + 1;
        return left>right ? left : right;    // 
    }
};

3. Validate Binary Search Tree(두 갈래 찾기 트리 검증)
영문:https://leetcode.com/problems/validate-binary-search-tree/
중국어 버전:https://leetcode-cn.com/problems/validate-binary-search-tree/

class Solution {
public:
 
    bool isValidBST(TreeNode* root) 
    {
        TreeNode *pre = NULL;       //pre ， 
        return validate(root, pre);
    }

    bool validate(TreeNode *root, TreeNode *&pre) //pre 
    {
        if (root == NULL)
            return true;
        if (!validate(root->left, pre))
            return false;
        if (pre != NULL && pre->val >= root->val)
            //  NULL 
            return false;
        pre = root;
        return validate(root->right, pre);
    }

};

4.Path Sum(경로 총계)
영문:https://leetcode.com/problems/path-sum/
중국어 버전:https://leetcode-cn.com/problems/path-sum/

class Solution{    // 
public:
    bool hasPathSum(TreeNode* root, int sum) { // 、 
            if (!root) return false;
            if (!root->left && !root->right && root->val == sum ) return true;
            return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
        }
};