算法刷题笔记--二叉树篇

感觉树这一章还是没搞清楚，可能是基础不扎实的缘故，学完C++巩固底层知识后二刷
理论基础

1. 确定递归函数的参数和返回值 :确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。

2. 确定终止条件 : 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。

3. 确定单层递归的逻辑:确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

涉及到二叉树的构造，无论普通二叉树还是二叉搜索树一定前序，都是先构造中节点。
求普通二叉树的属性，一般是后序，一般要通过递归函数的返回值做计算
求二叉搜索树的属性，一定是中序了，要不白瞎了有序性了。
注意在普通二叉树的属性中，我用的是一般为后序，例如单纯求深度就用前序
所以求普通二叉树的属性还是要具体问题具体分析。

二叉树的遍历方式

二叉树的前序遍历

左中右
递归法

class Solution {
public:
    void traversal(TreeNode* cur,vector<int>& vec){
        if(cur==nullptr){
            return;
        }
        vec.push_back(cur->val);
        traversal(cur->left,vec);
        traversal(cur->right,vec);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        traversal(root,res);
        return res;
    }
};

迭代法

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> vec;
        st.push(root);
        while(!st.empty()){
            TreeNode* node=st.top();
            st.pop();
            if(node!=nullptr){
                vec.push_back(node->val);
            }else{
                continue; 
            }
            st.push(node->right);
            st.push(node->left);
        }
        return vec;
    }
};

在遇到空指针时，这个方法会将空指针继续入栈，然后在下一轮循环中进行处理，这样会导致额外的空节点入栈和出栈操作，增加了不必要的计算开销。
改进的解法在遇到空指针时，直接跳过不处理，节省了这部分不必要的操作，提高了效率。
改进过的

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> vec;
        st.push(root);
        while(!st.empty()){
            TreeNode* node=st.top();
            st.pop();
            if(node!=nullptr){
                vec.push_back(node->val);
            }else{
                continue; 
            }
            if(node->right!=nullptr){
                st.push(node->right);
            }
            if(node->left!=nullptr){
                st.push(node->left);
            }
            
        }
        return vec;
    }
};

二叉树的中序遍历

左中右
递归法

class Solution {
public:
    void inorder(TreeNode* root,vector<int> &res){
        if(root==nullptr){
            return;
        }
        inorder(root->left,res);
        res.push_back(root->val);
        inorder(root->right,res);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        inorder(root,result);
        return result;
    }
};

前序遍历的代码，不能和中序遍历通用呢，因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。

那么再看看中序遍历，中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。

那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。

迭代法

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode* cur=root;
        while(cur!=nullptr||!st.empty()){
            if(cur!=nullptr){
                st.push(cur);
                cur=cur->left;
            }else{
                cur=st.top();
                st.pop();
                result.push_back(cur->val);
                cur=cur->right;
            }
        }
        return result;
    }
};

二叉树的后序遍历

左右中
递归法
在传递vector参数时注意要传递引用而不是值(前面要加&），如果传递值就不会改变vector里面的数据

class Solution {
public:
    void reverse(TreeNode* root,vector<int>& res){
        if(root==nullptr){
            return;
        }
        reverse(root->left,res);
        reverse(root->right,res);
        res.push_back(root->val);
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        reverse(root,result);
        return result;
    }
};

迭代法
先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了，如下图：

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        st.push(root);
        while(!st.empty()){
            TreeNode* node=st.top();
            st.pop();
            if(node!=nullptr){
                result.push_back(node->val);
            }else{
                continue;
            }
            if(node->left!=nullptr){
                st.push(node->left);
            }
            if(node->right!=nullptr){
                st.push(node->right);
            }
        }
        reverse(result.begin(),result.end());
        return result;

    }
};

求二叉树的属性

对称二叉树

首先想清楚，判断对称二叉树要比较的是哪两个节点，要比较的可不是左右节点！

对于二叉树是否对称，要比较的是根节点的左子树与右子树是不是相互翻转的，理解这一点就知道了其实我们要比较的是两个树（这两个树是根节点的左右子树），所以在递归遍历的过程中，也是要同时遍历两棵树。

比较的是两个子树的里侧和外侧的元素是否相等。

因为要遍历两棵树而且要比较内侧和外侧节点，所以准确的来说是一个树的遍历顺序是左右中，一个树的遍历顺序是右左中。

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root==nullptr){
            return true;
        }
        return compare(root->left,root->right);
    }
    bool compare(TreeNode* left,TreeNode*right){
        if(left==nullptr&&right!=nullptr){
            return false;
        }
        else if(left!=nullptr&&right==nullptr){
            return false;
        }
        else if(left==nullptr&&right==nullptr){
            return true;
        }else if(left->val!=right->val){
            return false;
        }
        bool outside=compare(left->left,right->right);
        bool inside=compare(left->right,right->left);
        bool result=inside&&outside;
        return result;

    }
};

二叉树的最大深度

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数

本题可以使用前序（中左右），也可以使用后序遍历（左右中），使用前序求的就是深度，使用后序求的是高度。

二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）

二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）

而根节点的高度就是二叉树的最大深度，所以本题中我们通过后序求的根节点高度来求的二叉树最大深度。

class Solution {
public:
    int getdepth(TreeNode* node) {
        if (node == NULL) return 0;
        int leftdepth = getdepth(node->left);       // 左
        int rightdepth = getdepth(node->right);     // 右
        int depth = 1 + max(leftdepth, rightdepth); // 中
        return depth;
    }
    int maxDepth(TreeNode* root) {
        return getdepth(root);
    }
};

二叉树的最小深度

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
如果不清楚题意可能会产生如下误区

如果这么求的话，没有左孩子的分支会算为最短深度。
所以，如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。
反之，右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。 最后如果左右子树都不为空，返回左右子树深度最小值 + 1 。

求二叉树的最小深度和求二叉树的最大深度的差别主要在于处理左右孩子不为空的逻辑。

class Solution {
public:
    int minDepth(TreeNode* root) {
        return getHeight(root);
    }
    int getHeight(TreeNode* node){
        if(node==nullptr){
            return 0;
        }
        int leftheight=getHeight(node->left);
        int rightheight=getHeight(node->right);
        if(node->left==nullptr&&node->right!=nullptr){
            return rightheight+1;
        }
        if(node->left!=nullptr&&node->right==nullptr){
            return leftheight+1;
        }
        int result=min(rightheight,leftheight)+1;
        return result;
    }
};

完全二叉树的节点个数

在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。
完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。

对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。

对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。
可以看出如果整个树不是满二叉树，就递归其左右孩子，直到遇到满二叉树为止，用公式计算这个子树（满二叉树）的节点数量。

这里关键在于如何去判断一个左子树或者右子树是不是满二叉树呢？

在完全二叉树中，如果递归向左遍历的深度等于递归向右遍历的深度，那说明就是满二叉树

class Solution {
public:
    int countNodes(TreeNode* root) {
        if(root==nullptr){
            return 0;
        }
        // 开始根据左深度和右深度是否相同来判断该子树是不是满二叉树
        TreeNode* left=root->left;
        TreeNode* right=root->right;
        int leftDepth=0;
        int rightDepth=0;
        while(left){
            left=left->left;
            leftDepth++;
        }
        while(right){
            right=right->right;
            rightDepth++;
        }
        if(leftDepth==rightDepth){
            return (2<<leftDepth)-1;
        }//第一种情况

        int leftTreeNum=countNodes(root->left);
        int rightTreeNum=countNodes(root->right);
        int result=leftTreeNum+rightTreeNum+1;
        return result;

    }
};

平衡二叉树

二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。

求深度可以从上到下去查 所以需要前序遍历（中左右），而高度只能从下到上去查，所以只能后序遍历（左右中）

如何判断以当前传入节点为根节点的二叉树是否是平衡二叉树呢？当然是其左子树高度和其右子树高度的差值。

分别求出其左右子树的高度，然后如果差值小于等于1，则返回当前二叉树的高度，否则返回-1，表示已经不是二叉平衡树了。

class Solution {
public:
    // 返回以该节点为根节点的二叉树的高度，如果不是平衡二叉树了则返回-1
    int getHeight(TreeNode* node){
        if(node==nullptr){
            return 0;
        }
        int leftheight=getHeight(node->left);
        if(leftheight==-1){
            return -1;
        }
        int rightheight=getHeight(node->right);
        if(rightheight==-1){
            return -1;
        }
        int result;
        if(abs(leftheight-rightheight)>1){
            result=-1;
        }else{
            result=1+max(leftheight,rightheight);
        }
        return result;
    }
    bool isBalanced(TreeNode* root) {
        return getHeight(root)==-1?false:true;
    }
    
};

找树左下角的值

在树的最后一行找到最左边的值。

首先要是最后一行，然后是最左边的值。

如果使用递归法，如何判断是最后一行呢，其实就是深度最大的叶子节点一定是最后一行。

所以要找深度最大的叶子节点。

那么如何找最左边的呢？可以使用前序遍历（当然中序，后序都可以，因为本题没有 中间节点的处理逻辑，只要左优先就行），保证优先左边搜索，然后记录深度最大的叶子节点，此时就是树的最后一行最左边的值。

class Solution {
public:
    int maxDepth(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != nullptr) {
            que.push(root);
        } else {
            return 0;
        }
        int result = 0;
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                if (node->left) {
                    que.push(node->left);
                }
                if (node->right) {
                    que.push(node->right);
                }
            }
            result++;
        }
        return result;
    }
};

二叉树的修改与构造

翻转二叉树

可以发现想要翻转它，其实就把每一个节点的左右孩子交换一下就可以了。

关键在于遍历顺序，前中后序应该选哪一种遍历顺序？ （一些同学这道题都过了，但是不知道自己用的是什么顺序）

遍历的过程中去翻转每一个节点的左右孩子就可以达到整体翻转的效果。

注意只要把每一个节点的左右孩子翻转一下，就可以达到整体翻转的效果

这道题目使用前序遍历和后序遍历都可以，唯独中序遍历不方便，因为中序遍历会把某些节点的左右孩子翻转了两次！建议拿纸画一画，就理解了

那么层序遍历可以不可以呢？依然可以的！只要把每一个节点的左右孩子翻转一下的遍历方式都是可以的！
前序
递归法

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root==nullptr){
            return root;
        }
        swap(root->left,root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
    
};

从中序与后序遍历序列构造二叉树

理论知识大家应该都清楚，就是以 后序数组的最后一个元素为切割点，先切中序数组，根据中序数组，反过来再切后序数组。一层一层切下去，每次后序数组最后一个元素就是节点元素。

• 第一步：如果数组大小为零的话，说明是空节点了。

• 第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。

• 第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点

• 第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）

• 第五步：切割后序数组，切成后序左数组和后序右数组

• 第六步：递归处理左区间和右区间

中序数组相对比较好切，找到切割点（后序数组的最后一个元素）在中序数组的位置，然后切割

首先后序数组的最后一个元素指定不能要了，这是切割点 也是 当前二叉树中间节点的元素，已经用了

后序数组没有明确的切割元素来进行左右切割，不像中序数组有明确的切割点，切割点左右分开就可以了。

此时有一个很重的点，就是中序数组大小一定是和后序数组的大小相同的（这是必然）。

中序数组我们都切成了左中序数组和右中序数组了，那么后序数组就可以按照左中序数组的大小来切割，切成左后序数组和右后序数组。

此时，中序数组切成了左中序数组和右中序数组，后序数组切割成左后序数组和右后序数组。

class Solution {
public:
    TreeNode* setTree(vector<int>& inorder, vector<int>& postorder) {
        if(postorder.size()==0){
            return nullptr;
        }
        //如果数组大小为零的话，说明是空节点了。
        int rootvalue=postorder[postorder.size()-1];
        TreeNode* node=new TreeNode(rootvalue);
        //如果不为空，那么取后序数组最后一个元素作为节点元素
        if(postorder.size()==1){
            return node;
        }
        int i;
        for(i=0;i<inorder.size();i++){
            if(inorder[i]==rootvalue){
                break;
            }
        }
        //找到后序数组最后一个元素在中序数组的位置，作为切割点

        vector<int> leftinorder(inorder.begin(),inorder.begin()+i);
        vector<int> rightinorder(inorder.begin()+i+1,inorder.end());
        //切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
        postorder.resize(postorder.size()-1);
        vector<int> leftpostorder(postorder.begin(),postorder.begin()+leftinorder.size());
        vector<int> rightpostorder(postorder.begin()+leftinorder.size(),postorder.end());
        //切割后序数组，切成后序左数组和后序右数组
        node->left=setTree(leftinorder,leftpostorder);
        node->right=setTree(rightinorder,rightpostorder);
        //递归处理左区间和右区间

        return node;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(inorder.size()==0||postorder.size()==0){
            return nullptr;
        }
        return setTree(inorder,postorder);
    }

};

最大二叉树

给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：

二叉树的根是数组中的最大元素。
左子树是通过数组中最大值左边部分构造出的最大二叉树。
右子树是通过数组中最大值右边部分构造出的最大二叉树。

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        TreeNode* node=new TreeNode(0);
        if(nums.size()==1){
            node->val=nums[0];
            return node;
        }
        //先要找到数组中最大的值和对应的下标， 最大的值构造根节点，下标用来下一步分割数组。
        int maxValue=0;
        int maxValueIndex=0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]>maxValue){
                maxValue=nums[i];
                maxValueIndex=i;
            }
        }
        
        node->val=maxValue;
        //最大值所在的下标左区间 构造左子树
        if(maxValueIndex>0){
            vector<int> newVec(nums.begin(),nums.begin()+maxValueIndex);
            node->left=constructMaximumBinaryTree(newVec);
        }
        if(maxValueIndex<(nums.size()-1)){
            vector<int> newVec(nums.begin()+maxValueIndex+1,nums.end());
            node->right=constructMaximumBinaryTree(newVec);
        }
        return node;
    }
};

注意类似用数组构造二叉树的题目，每次分隔尽量不要定义新的数组，而是通过下标索引直接在原数组上操作，这样可以节约时间和空间上的开销。

一些同学也会疑惑，什么时候递归函数前面加if，什么时候不加if，这个问题我在最后也给出了解释。

其实就是不同代码风格的实现，一般情况来说：如果让空节点（空指针）进入递归，就不加if，如果不让空节点进入递归，就加if限制一下， 终止条件也会相应的调整。

二叉搜索树中的搜索

二叉搜索树是一个有序树：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉搜索树
这就决定了，二叉搜索树，递归遍历和迭代遍历和普通二叉树都不一样。

递归

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(root==nullptr||root->val==val){
            return root;
        }
        TreeNode* result=nullptr;
        if(val<root->val){
            result=searchBST(root->left,val);
        }
        if(val>root->val){
            result=searchBST(root->right,val);
        }
        return result;
    }
};

迭代

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        while(root!=nullptr){
            if(root->val<val){
                root=root->right;
            }else if(root->val>val){
                root=root->left;
            }else{
                return root;
            }
        }
        return root;
    }
};

求二叉搜索树的属性

二叉搜索树的最小绝对差

题目中要求在二叉搜索树上任意两节点的差的绝对值的最小值。

注意是二叉搜索树，二叉搜索树可是有序的。

遇到在二叉搜索树上求什么最值啊，差值之类的，就把它想成在一个有序数组上求最值，求差值，这样就简单多了。

class Solution {
public:
    int result=INT_MAX;
    TreeNode* pre=nullptr;
    void traversal(TreeNode* cur){
        if(cur==nullptr){
            return;
        }
        traversal(cur->left);
        if(pre!=nullptr){
           result=min(result,cur->val-pre->val);
        }
        pre=cur;
        traversal(cur->right);
    }
    int getMinimumDifference(TreeNode* root) {
       traversal(root);
       return result;
    }
};

二叉搜索树中的众数

既然是搜索树，它中序遍历就是有序的。
因此众数都是连续出现的

遍历有序数组的元素出现频率，从头遍历，那么一定是相邻两个元素作比较，然后就把出现频率最高的元素输出就可以了。

弄一个指针指向前一个节点，这样每次cur（当前节点）才能和pre（前一个节点）作比较。
而且初始化的时候pre = NULL，这样当pre为NULL时候，我们就知道这是比较的第一个元素。
如果 频率count 等于 maxCount（最大频率），当然要把这个元素加入到结果集中
频率count 大于 maxCount的时候，不仅要更新maxCount，而且要清空结果集（以下代码为result数组），因为结果集之前的元素都失效了。

class Solution { // 二叉搜索树的特性：众数都是连续出现的
public:
    int maxcount = 0;
    int count = 0;
    TreeNode* pre = nullptr;
    vector<int> result; // 结果集
    void traversal(TreeNode* cur) {
        if (cur == nullptr) {
            return;
        }
        traversal(cur->left);

        if (pre == nullptr) {
            count = 1;
        } else if (pre->val == cur->val) {
            count++;
        } else {
            count = 1;
        }
        pre = cur;
        if (count == maxcount) {
            result.push_back(cur->val);
        } else if (count > maxcount) {
            maxcount = count;
            result.clear();
            result.push_back(cur->val);
        }
        traversal(cur->right);
        return;
    }
    vector<int> findMode(TreeNode* root) {
        count = 0;
        maxcount = 0;
        pre = nullptr;
        result.clear();
        traversal(root);
        return result;
    }
};

二叉树公共祖先问题

二叉树的最近公共祖先

求最小公共祖先，需要从底向上遍历，那么二叉树，只能通过后序遍历（即：回溯）实现从底向上的遍历方式。
如果left 和 right都不为空，说明此时root就是最近公共节点。这个比较好理解

如果left为空，right不为空，就返回right，说明目标节点是通过right返回的，反之依然。

在回溯的过程中，必然要遍历整棵二叉树，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的left和right）做逻辑判断。

在递归函数有返回值的情况下：如果要搜索一条边，递归函数返回值不为空的时候，立刻返回，如果搜索整个树，直接用一个变量left、right接住返回值，这个left、right后序还有逻辑处理的需要，也就是后序遍历中处理中间节点的逻辑（也是回溯）。

不太理解怎么回溯可以照着代码画图自行理解

public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==q||root==p||root==nullptr){
            return root;
        }
        TreeNode* left=lowestCommonAncestor(root->left,p,q);
        TreeNode* right=lowestCommonAncestor(root->right,p,q);
        if(left!=nullptr&&right==nullptr){
            return left;
        }else if(left==nullptr&&right!=nullptr){
            return right;
        }else if(left!=nullptr&&right!=nullptr){
            return root;
        }else{
            return nullptr;
        }
    }
};

二叉树搜索树的最近公共祖先

p、q 为不同节点且均存在于给定的二叉搜索树中。也就是说一定会找到公共祖先的，所以并不存在遇到空的情况。

在遍历二叉搜索树的时候就是寻找区间[p->val, q->val]（注意这里是左闭又闭）

那么如果 cur->val 大于 p->val，同时 cur->val 大于q->val，那么就应该向左遍历（说明目标区间在左子树上）。

需要注意的是此时不知道p和q谁大，所以两个都要判断
如果 cur->val 小于 p->val，同时 cur->val 小于 q->val，那么就应该向右遍历（目标区间在右子树）。

剩下的情况，就是cur节点在区间（p->val <= cur->val && cur->val <= q->val）或者 （q->val <= cur->val && cur->val <= p->val）中，那么cur就是最近公共祖先了，直接返回cur。

class Solution {
public:
    TreeNode* traversal(TreeNode* cur,TreeNode* p,TreeNode*q){
        if(cur==nullptr){
            return cur;
        }
        if(cur->val>p->val&&cur->val>q->val){
            TreeNode* left=traversal(cur->left,p,q);
            if(left!=nullptr){
                return left;
            }
        }
        if(cur->val<p->val&&cur->val<q->val){
            TreeNode* right=traversal(cur->right,p,q);
            if(right!=nullptr){
                return right;
            }
        }
        return cur;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return  traversal(root,p,q);
    }
};

二叉搜索树的修改与构造

二叉搜索树中的插入操作

只要按照二叉搜索树的规则去遍历，遇到空节点就插入节点就可以了。
可以利用返回值完成新加入的节点与其父节点的赋值操作
终止条件就是找到遍历的节点为null的时候，就是要插入节点的位置了，并把插入的节点返回。
下一层将加入节点返回，本层用root->left或者root->right将其接住。

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root==nullptr){
            TreeNode* node=new TreeNode(val);
            return node;
        }
        if(val>root->val){
            root->right=insertIntoBST(root->right,val);
        }
        if(val<root->val){
            root->left=insertIntoBST(root->left,val);
        }
        return root;
    }
};

删除二叉搜索树中的节点

1.找到需要删除的节点
2.删除他
3.返回删除节点位置上的新节点

有以下五种情况：
第一种情况：没找到删除的节点，遍历到空节点直接返回了
找到删除的节点
第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(root==nullptr){
            return nullptr;
        }
        if(root->val==key){
            if(root->left==nullptr&&root->right==nullptr){
                //左右孩子都为空
                delete root;
                return nullptr;
            }
            else if(root->left!=nullptr&&root->right==nullptr){
                //其右孩子为空，左孩子不为空
                auto retNode =root->left;
                delete root;
                return retNode;
            }
            else if(root->left==nullptr&&root->right!=nullptr){
                //其左孩子为空，右孩子不为空
                auto retNode=root->right;
                delete root;
                return retNode;
            }
            else{
                //左右孩子节点都不为空
                TreeNode* cur=root->right;
                while(cur->left){
                    cur=cur->left;
                }
                cur->left=root->left;
                TreeNode* temp=root;
                root=root->right;
                delete temp;
                return root;
            }
        }
        if(root->val>key){
            root->left=deleteNode(root->left,key);
        }
        if(root->val<key){
            root->right=deleteNode(root->right,key);
        }
        return root;
    }
};

修剪二叉搜索树

理解了最关键部分了我们再递归三部曲：

确定递归函数的参数以及返回值
这里我们为什么需要返回值呢？

因为是要遍历整棵树，做修改，其实不需要返回值也可以，我们也可以完成修剪（其实就是从二叉树中移除节点）的操作。

但是有返回值，更方便，可以通过递归函数的返回值来移除节点。

确定终止条件
修剪的操作并不是在终止条件上进行的，所以就是遇到空节点返回就可以了。

确定单层递归的逻辑
如果root（当前节点）的元素小于low的数值，那么应该递归右子树，并返回右子树符合条件的头结点。
如果root(当前节点)的元素大于high的，那么应该递归左子树，并返回左子树符合条件的头结点。
接下来要将下一层处理完左子树的结果赋给root->left，处理完右子树的结果赋给root->right。

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if(root==nullptr){
            return nullptr;
        }
        if(root->val<low){
        //如果root（当前节点）的元素小于low的数值，那么应该递归右子树，并返回右子树符合条件的头结点。
            TreeNode* right=trimBST(root->right,low,high);
            return right;
        }
        if(root->val>high){
        //如果root(当前节点)的元素大于high的，那么应该递归左子树，并返回左子树符合条件的头结点。
            TreeNode* left=trimBST(root->left,low,high);
            return left;
        }
        //接下来要将下一层处理完左子树的结果赋给root->left，处理完右子树的结果赋给root->right。
        root->left=trimBST(root->left,low,high);
        root->right=trimBST(root->right,low,high);
        return root;
    }
};

将有序数组转换为二叉搜索树

数组构造二叉树，构成平衡树是自然而然的事情，因为大家默认都是从数组中间位置取值作为节点元素，一般不会随机取。所以想构成不平衡的二叉树是自找麻烦。

如果根据数组构造一棵二叉树。本质就是寻找分割点，分割点作为当前节点，然后递归左区间和右区间。

分割点就是数组中间位置的节点。

那么为问题来了，如果数组长度为偶数，中间节点有两个，取哪一个？

取哪一个都可以，只不过构成了不同的平衡二叉搜索树。

class Solution {
public:
    TreeNode* traveral(vector<int>&nums,int left,int right){
        if(left>right){
            return nullptr;
        }
        int mid=(left+right)/2;
        TreeNode* root=new TreeNode(nums[mid]);
        root->left=traveral(nums,left,mid-1);
        root->right=traveral(nums,mid+1,right);
        return root;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        TreeNode* root=traveral(nums,0,nums.size()-1);
        return root;
        
    }
};

把二叉搜索树转换为累加树

换一个角度来看，这就是一个有序数组[2, 5, 13]，求从后到前的累加数组，也就是[20, 18, 13]，是不是感觉这就简单了。
从树中可以看出累加的顺序是右中左，所以我们需要反中序遍历这个二叉树，然后顺序累加就可以了。

class Solution {
public:
    int pre=0;
    void traversal(TreeNode* cur){
        if(cur==nullptr){
            return;
        }
        traversal(cur->right);
        cur->val+=pre;
        pre=cur->val;
        traversal(cur->left);
    }
    TreeNode* convertBST(TreeNode* root) {
        pre=0;
        traversal(root);
        return root;
    }
};