二叉树 堆 2019-04-17

二叉树

1. 实现一个二叉查找树，并且支持插入、删除、查找操作

2. 实现查找二叉查找树中某个节点的后继、前驱节点

3. 实现二叉树前、中、后序以及按层遍历

4. 并完成leetcode上的验证二叉搜索树(98)及二叉树 层次遍历(102,107)！（选做）（保留往期第四天任务）注：这个跟下面的习题有重复**

堆

1. 实现一个小顶堆、大顶堆、优先级队列

2. 实现堆排序

3. 利用优先级队列合并 K 个有序数组

4. 求一组动态数据集合的最大 Top K

5. （选做）第三天堆排序学习（复习）

对应的 LeetCode 练习题

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<TreeNode*> 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);
        }
};