传送门：y总讲解视频——LeetCode暑期刷题打卡2019——Week3 树专题

补数据结构-树中：想刷完leetcode中所有树的题目。(PTA也想补一下)

98. 验证二叉搜索树

二叉搜索树的特点：左 < 根 < 右，由此递归确定每个结点的值是否在合理范围内

94. 二叉树的中序遍历

手动模拟递归的过程，用栈来维护。由于中序遍历是先递归左子树，所以在栈中要先压入左子树

101. 对称二叉树

迭代的方式遍历：左半边是左根右，右半边是右根左，承接上题

105. 从前序与中序遍历序列构造二叉树

先用哈希表记录根节点在中序遍历中的位置，再递归处理左半边和右半边，通过给dfs传参数范围

102. 二叉树的层序遍历

宽搜框架，但要先记录每一层有多少个元素

236. 二叉树的最近公共祖先

算法1：递归；算法2：向上搜索(这里是O(n),听说还有LCA倍增写法，等学会了更新)

算法1：递归（递归函数主要在于出口,这里递归函数比较难想）

/**
 * 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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root || root==p || root==q) return root;

        auto left = lowestCommonAncestor(root->left,p,q);
        auto right = lowestCommonAncestor(root->right,p,q);
        if(!left) return right;
        if(!right) return left;
        return root;
    }
};

算法2：向上搜索（更优化的写法是LCA倍增？）

/**
 * 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:

    unordered_map<int,TreeNode*> fa;
    unordered_map<int,bool> vis;

    void dfs(TreeNode* root)
    {
        if(root->left){
            fa[root->left->val] = root;
            dfs(root->left);
        }
        if(root->right){
            fa[root->right->val] = root;
            dfs(root->right);
        }
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        fa[root->val] = NULL;
        dfs(root); // 向上搜索，建立父指针
        while(p != NULL){
            vis[p->val] = true;
            p = fa[p->val];
        }

        while(q != NULL){
            if(vis[q->val]) return q;
            q = fa[q->val];
        }

        return NULL;
    }
};

543. 二叉树的直径

递归定义：返回当前结点向下走的最大深度

124. 二叉树中的最大路径和

递归定义：返回当前节点最大路径和，承接上题

173. 二叉搜索树迭代器

因为是二叉搜索树，有如下特点：左 < 根 < 右,按照中序遍历的方式即可

297. 二叉树的序列化与反序列化

序列化：将值转换为字符串

-------------------------------------------------------------------------------update : 2020/6/5

700. 二叉搜索树中的搜索

递归查找

701. 二叉搜索树中的插入操作

递归插入左子树或右子树

450. 删除二叉搜索树中的节点

情况1：当前结点没有左右子树，直接删除
情况2：当前结点只有左子树或右子树，直接返回左子树或右子树
情况2：当前结点既有左子树又有右子树，将当前结点与左子树中的最大元素交换，或右子树中的最小元素交换

/**
 * 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* deleteNode(TreeNode* root, int key) {
        if(root == NULL) return NULL;

        if(key < root->val) root->left = deleteNode(root->left,key);
        else if(key > root->val) root->right = deleteNode(root->right,key);
        else
        {
            if(!root->left && !root->right) return NULL;
            else if(!root->left) return root->right;
            else if(!root->right) return root->left;
            else
            {
                TreeNode* temp = root->right;
                while(temp->left) temp = temp->left;
                swap(root->val,temp->val);
                root->right = deleteNode(root->right,key);
            }
        }

        return root;
    }
};

-------------------------------------------------------------------------------update : 2020/6/6