6.二叉树.题目3

题目

17.二叉搜索树中的众数

（题目链接）
给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素。
首先如果不是二叉搜索树的话，应该怎么解题，是二叉搜索树，又应该如何解题，两种方式做一个比较，可以加深大家对二叉树的理解。

• 如果不是二叉搜索树：最直观的办法是先将树遍历一遍，再使用map统计频率，然后把频率排序，最后取高频的元素的集合

/* 表示在排序时，a应该排在b前面。
 因此，当我们使用这个函数对vector>进行排序时，频率最高的元素会被放在前面*/
bool static cmp (const pair<int, int>& a, const pair<int, int>& b) {
    return a.second > b.second;
}

    vector<int> findMode(TreeNode* root) {
        unordered_map<int, int> map; // key:元素，value:出现频率
        vector<int> result;
        if (root == NULL) return result;
        // 遍历树，并将树出现频率统计在map中
        searchBST(root, map);
        vector<pair<int, int>> vec(map.begin(), map.end());
        sort(vec.begin(), vec.end(), cmp); // 给频率排个序
        result.push_back(vec[0].first);
        for (int i = 1; i < vec.size(); i++) {
            // 取最高的放到result数组中
            if (vec[i].second == vec[0].second) result.push_back(vec[i].first);
            else break;
        }
        return result;
    }

• 如果是二叉搜索树：将二叉搜索树通过中序遍历展开为递增序列，然后通过一次遍历即可把众数放入数组res中。使用了pre指针和cur指针的技巧。使用一个指针指向前一个节点，这样每次cur（当前节点）才能和pre（前一个节点）作比较。

private:
    int maxcount = 0;
    int count = 0;
    TreeNode* pre = nullptr;
    std::vector<int> res;

    void backtracking(TreeNode* root){
        if(root==nullptr) return;
        backtracking(root->left);
        // 根据pre，root修改计数count
        if(pre==nullptr) count=1;
        else if(pre->val==root->val) count++;
        else count=1; 
        pre = root; // 更新pre的指针位置
        
        if(count==maxcount) res.push_back(root->val);
        if(count>maxcount){
            res.clear();
            maxcount = count;
            res.push_back(root->val);
        }

        backtracking(root->right);
        return;
    }
public:
    vector<int> findMode(TreeNode* root) {
        res.clear();
        backtracking(root);
        return res;
    }

---

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

（题目链接）
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。最近公共祖先的定义：对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。说明：所有节点的值都是唯一的；p、q 为不同节点且均存在于给定的二叉树中。
寻找最近公共祖先节点，需要我们从二叉树的底部往顶部进行处理，这就需要使用后序遍历的方法（左右上）
终止条件：当cur==nullptr，以及当cur==p || q说明也遍历到了目标节点，到达叶子节点位置时结束
确定单层递归逻辑-本题的递归函数有返回值，因为回溯的过程需要递归函数的返回值做判断，而递归函数有返回值就是要遍历某一条边，但有返回值也要看如何处理返回值。

// 搜索一条边
if (递归函数(root->left)) return ;
if (递归函数(root->right)) return ;
// 搜索整个树
left = 递归函数(root->left);  // 左
right = 递归函数(root->right); // 右
left与right的逻辑处理;         // 中 

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

    TreeNode* backtracking(TreeNode* root, TreeNode* p, TreeNode* q){
    	// 终止条件
        if(root==nullptr) return root;
        if(root==p || root==q) return root;

        TreeNode* left = backtracking(root->left, p, q);
        TreeNode* right = backtracking(root->right, p, q);
        // 后序遍历，中序需要左，右子树的值进行判断
        if(left!=nullptr && right!=nullptr) return root;
        else if(left==nullptr && right!=nullptr) return right;
        else if(left!=nullptr && right==nullptr) return left;
        else return nullptr;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return backtracking(root, p, q);
    }

---

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

（题目链接）
因为是有序树，所以 如果 中间节点是 q 和 p 的公共祖先，那么 中节点的数组 一定是在 [p, q]区间的。那么只要从上到下去遍历，遇到 cur节点是数值在[p, q]区间中则一定可以说明该节点cur就是p 和 q的公共祖先，那么该如何判断是最近祖先？

跟据以上的例子，所以当我们从上向下去递归遍历，第一次遇到 cur节点是数值在[q, p]区间中，那么cur就是 q和p的最近公共祖先。

    TreeNode* backtracking(TreeNode* root, TreeNode* p, TreeNode* q){
        if(root==nullptr) return root;

        if(root->val>p->val && root->val>q->val){
            TreeNode* left = backtracking(root->left, p, q);
            if(left!=nullptr) return left;
        }

        if(root->val<p->val && root->val<q->val){
            TreeNode* right = backtracking(root->right, p, q);
            if(right!=nullptr) return right;
        }
        return root;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return backtracking(root, p, q);
    }

---

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

（题目链接）
给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证：新值和原始二叉搜索树中的任意节点值都不同。其实只要遍历二叉搜索树，找到空节点 插入元素就可以了，那么这道题其实就简单了。
递归函数设置返回值，可以利用返回值完成新加入的节点与其父节点的赋值操作；
终止条件：当cur==nullptr，到达叶子节点位置时结束，就是要插入新节点的位置，并把插入的节点返回。
单层递归的逻辑：二叉搜索树的递归方向，根据val值与root->val的比值大小

	// 递归函数设置返回值，用于终止条件时新节点的赋值
    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); //在终止条件时完成对root的插入新子节点
        if(val<root->val) root->left = insertIntoBST(root->left, val);
        return root;
    }

当然该递归函数也可不设置返回值，需要记录每次递归前上一个节点（parent），遇到空节点了，就让parent左孩子或者右孩子指向新插入的节点。然后结束递归。

	// 递归函数不设置返回值，需要外部指针记录父节点
    TreeNode* par;
    void backtracking(TreeNode* root, int val){
        if(root==nullptr){
            TreeNode* node = new TreeNode(val);
            if(val>par->val) par->right = node;
            else par->left = node;
            return;
        }

        par = root; //不需要回溯，只需记录每次递归的父节点
        if(val>root->val) backtracking(root->right, val);
        if(val<root->val) backtracking(root->left, val);
        return;
    }
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        par = new TreeNode(val);
        if(root==nullptr){
            root = new TreeNode(val);
        }
        backtracking(root, val);
        return root;
    }	

普通二叉树的删除方式

对于没有数值大小排序需要的普通二叉树，通用的二叉树的删除方法。主要分为两个步骤

1. 和目标节点的右子树最左面节点交换
2. 直接用nullptr覆盖

	// 比较绕，需要思考以西。
  TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) return root;
        if (root->val == key) {
            if (root->right == nullptr) { // 这里第二次操作目标值：最终删除的作用
                return root->left;
            }
            TreeNode *cur = root->right;
            while (cur->left) {
                cur = cur->left;
            }
            swap(root->val, cur->val); // 这里第一次操作目标值：交换目标值其右子树最左面节点。
        }
        root->left = deleteNode(root->left, key);
        root->right = deleteNode(root->right, key);
        return root;
    }

---

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

（题目链接）
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。删除节点分为两个步骤：1.找到要删除的节点 2.删除元素。但搜索二叉树的删除节点要比普通的二叉树复杂多，因此涉及要删除节点的子树的重新排序的问题。
递归函数参数，返回值：
终止条件：当cur==nullptr，到达叶子节点位置时结束
每层递归逻辑：得分情况处理（处理是在父节点parent层处理的）

• 根据key，没有找到要删除的节点，不用处理，遍历到空节点就返回了
• 左右子节点都为空，则直接删除该节点
• 左节点为空，右节点非空，删除该节点，右节点补位
• 右节点为空，左节点非空，删除该节点，左节点补位
• 左右节点为非空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。(这样操作的目的是二叉搜索树的右子树的元素是均大于左子树的元素的，而右子树的的最小值必在最深的左叶子节点处，因此若删除父节点，则可以很自然地把左子树的头节点接到右子树的最深左叶子节点的left端)

    TreeNode* deleteNode(TreeNode* root, int key) {
        if(root==nullptr) return root;
        // 处理节点 因为递归函数有返回值-实现父节点修改处理
        if(root->val == key){
            if(root->left==nullptr && root->right==nullptr){
                delete root;
                return nullptr;
            }
            else if(root->left==nullptr && root->right!=nullptr){
                auto node = root->right;
                delete root;
                return node;
            }
            else if(root->right==nullptr && root->left!=nullptr){
                auto node = root->left;
                delete root;
                return node;
            }
            else{
                auto node = root->right;
                while(node->left!=nullptr) node=node->left;
                node->left = root->left;
                TreeNode* tmp = root;
                root = root->right;
                delete tmp; //释放原本root的内存
                return root;
            }
        }
        //指定递归的方向
        if(root->val>key) root->left = deleteNode(root->left, key);
        if(root->val<key) root->right = deleteNode(root->right, key);
        return root;
    }

---

22.修剪二叉树

（题目链接）
给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L)。可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。
递归函数确定参数，返回值：有返回值，更方便，可以通过递归函数的返回值来移除节点（返回值是为了这一点服务的）；
终止条件：当root==nullptr
单层递归的逻辑：1. （本层）如果root（当前节点）的元素小于low的数值，那么应该递归右子树，并返回右子树符合条件的头结点；如果root(当前节点)的元素大于high的，那么应该递归左子树，并返回左子树符合条件的头结点。2.（下一层）接下来要将下一层处理完左子树的结果赋给root->left，处理完右子树的结果赋给root->right。

    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if(root==nullptr) return nullptr;
        // 处理节点，相当于局部调整root节点附近
        if(root->val<low){
            TreeNode* right = trimBST(root->right, low, high);
            return right;
        }
        if(root->val>high){
            TreeNode* left = trimBST(root->left, low, high);
            return left;
        }
        root->left = trimBST(root->left, low, high);
        root->right = trimBST(root->right, low, high);
        return root;
    }

---

23.将有序数组转化为二叉搜索树

（题目链接）
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。高度平衡二叉树指：一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。

做这道题目需要了解：1.从中序后序遍历序列构造二叉树，最大二叉树，二叉搜索树中的插入操作；删除二叉搜索数中的节点。其实数组构造二叉树，构成平衡树是自然而然的事情，因为大家默认都是从数组中间位置取值作为节点元素，一般不会随机取。
本质就是寻找分割点，分割点作为当前节点，然后递归左区间和右区间。但数组长度为偶数，中间节点有两个，取不同的作为根节点，会造成不同的平衡二叉搜索树。

递归函数参数和返回值：首先是传入数组，然后就是左下标left和右下标right；在构造二叉树的时候尽量不要重新定义左右区间数组，而是用下标来操作原数组，此处定义使用的是左闭右闭区间。
递归终止条件：当区间left > right的时候，就是空节点了
确定单层递归逻辑：所以可以这么写：int mid = left + ((right - left) / 2);出于考虑right+left可能会出现越界的问题。取了中间位置，就开始以中间位置的元素构造节点，然后接着划分区间，root的左孩子接住下一层左区间的构造节点，右孩子接住下一层右区间构造的节点。最后返回root。
递归法

    TreeNode* traversal(std::vector<int>& nums, int left, int right){
        // 切割问题，根据区间下标返回
        if(left>right) return nullptr;
        int mid = left + (right-left)/2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = traversal(nums, left, mid-1);
        root->right = traversal(nums, mid+1, right);
        return root; 
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return traversal(nums, 0, nums.size()-1);
    }

不断中间分割，然后递归处理左区间，右区间，也可以说是分治；这需要应该对通过递归函数的返回值来增删二叉树很熟悉了，这也是常规操作。

---

24.把二叉搜索树转化为累加树

（题目链接）
给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。提示：树中的节点数介于 0 和 104 之间；每个节点的值介于 -104 和 104 之间；树中的所有值 互不相同；给定的树为二叉搜索树。

从树中可以看出累加的顺序是右中左，所以我们需要反中序遍历这个二叉树，然后顺序累加就可以了。本题依然需要一个pre指针记录当前遍历节点cur的前一个节点，这样才方便做累加——采用pre指针的题目还有1.搜索树的最小绝对值差，2.我的众数
递归函数参数和返回值：不需要返回值，只需要使用pre记录前一个节点的val作累加
终止条件：当cur==nullptr即可终止
单层递归的逻辑：遵循右中左遍历顺序，中间节点的操作是赋值为当前值+pre的值，并且更新pre值
递归法

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

迭代法-深度优先

---

总结

求最小公共祖先：

1. 需要从底向上遍历，那么二叉树，只能通过后序遍历（即：回溯）实现从底向上的遍历方式。
2. 在回溯的过程中，必然要遍历整棵二叉树，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的left和right）做逻辑判断
3. 要理解如果返回值left为空，right不为空为什么要返回right，为什么可以用返回right传给上一层结果

添加，删除二叉树节点：

1. 二叉搜索树删除节点比增加节点复杂的多，二叉搜索树添加节点只需要在叶子上添加就可以的，不涉及到结构的调整，而删除节点操作涉及到结构的调整。
2. 删除节点，最关键的部分是处理该节点左右节点都存在的情况。