代码随想录算法训练营第十天|二叉树完结

Leecode 617.合并二叉树

链接：https://leetcode.cn/problems/merge-two-binary-trees/

有个细节会决定题目简单或者复杂，按照题意我们是要构造一个新的二叉树，那么实际上我们是在既有的子树上构造新的二叉树，还是构造一颗与两个子树完全不同的二叉树呢？

事实证明第二种方法要简单很多

每次同时往下遍历的时候，如果两个指针都为空，那么我们就传空；如果两个指针有一个为空，另外一个不为空，那么我们就传递不为空的那个指针；如果两个节点都不为空，我们就创建一个新的节点用来存储两个节点的val值，所以函数的返回值我们用传递指针的方式比较容易实现

至于遍历方式其实是无所谓的，因为题目给我们的两颗树都是同时遍历的

 // 怎么做？如果是空节点就返回，如果两个节点有一个节点不空我们就继续做
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(root1 == NULL && root2 == NULL) return NULL;
        if(root1 == NULL) return root2;
        if(root2 == NULL) return root1;

        TreeNode *cur = new TreeNode(0); // 如果两个节点都不为空，那么我们要马上返回这个节点吗？
        // 是不是还要往下递归呀，确实！
        cur -> val = root1->val + root2 -> val;

        cur -> left = mergeTrees(root1 -> left,root2 -> left);
        cur -> right = mergeTrees(root1 -> right,root2 -> right);
        
        return cur;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Leecode 700. 二叉搜索树中的搜索

链接：https://leetcode.cn/problems/search-in-a-binary-search-tree/

先看普通的做法

 // 开始搜索，如果搜到了这个节点直接返回这个节点就OK了，所以题目给的函数就直接可以用
 // 那么这个节点需要被接住吗，是需要的，因为是逐层返回，所以需要被接住
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(root == NULL) return NULL;

        if(root -> val == val) return root;

        root -> left = searchBST(root -> left,val);
        root -> right = searchBST(root -> right,val);

        if(root -> left != NULL)  return root -> left; // 我们是用左右子树接住了返回结果，所以如果左右子树一旦有值，就直接返回
        if(root -> right != NULL) return root -> right;

        // 如果左右子树都没有返回结果我们就直接返回NULL，因为当前节点也肯定不是目标节点
        return NULL;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

也可以利用二叉搜索树的性质：

1. 如果当前节点的值大于目标节点的值，那么目标节点就在当前节点的左子树
2. 如果当前节点的值小于目标节点的值，那么目标节点就在当前节点的右子树

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(root == NULL) return NULL; // 这句话是少不了的
        if(root -> val == val) return root;

        
        if(root -> val > val) {root -> left =  searchBST(root -> left,val); if(root -> left != NULL) return root -> left;}
        if(root -> val < val) {root -> right = searchBST(root -> right,val); if(root -> right != NULL) return root -> right;}

        return NULL;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

Leecode 98. 验证二叉搜索树

链接：https://leetcode.cn/problems/validate-binary-search-tree/

首先先看题目定义：左子树的值全部小于父节点的值，右子树的值全部大于父节点的值

要做二叉搜索树，我们还是用左中右（也就是中序遍历）的方式去遍历，这样能够保证递归到的值是单调递增的，那么我们只要保证当前的值是大于前一个值的就OK

二叉树章节刚开始，我们做了一些递归实现前中后序遍历的题目，其实还是比较简单的

class Solution {
public:
    TreeNode * node = NULL;
    bool isValidBST(TreeNode* root) {
        if(root == NULL) return true; // 这里需要特别注意，如果当前节点是空我们直接返回true
        // 然后遍历左子树
        bool left = isValidBST(root -> left);
        // 中序遍历就是在递归左侧结束的时候，操作节点，此时如果该节点有右子树，那么会处理完自己后再去处理右子树，所以是左 -> 中 -> 右
        if(node != NULL && node -> val >= root -> val) return false;
        node = root;
        bool right = isValidBST(root -> right);

        return left && right;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

我们也可以直接上统一迭代法中的中序遍历，得到一个数组，并且判断数组是单调递增的，这道题也可以解

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if(root == NULL) return true;
        // 我们创建一个栈，用来存放节点，再创建一个vector，用来存保存好的所有节点的值
        vector<int> res;
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty())
        {
            // 并不是遍历，而是每次取出一个节点
            TreeNode *cur = st.top();
            if(cur!= NULL)
            {
                st.pop(); // 先弹出去，然后分别加入右儿子，该节点和NULL，和左儿子
                if(cur -> right != NULL) st.push(cur -> right);

                st.push(cur);
                st.push(NULL);

                if(cur -> left != NULL) st.push(cur -> left);
            }
            else
            {
                st.pop();
                TreeNode * now = st.top();
                st.pop();
                res.push_back(now -> val);
            }
        }
        for(int i=1;i<res.size();i++) if(res[i] <= res[i-1]) return false;

        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

Leecode 530. 二叉搜索树的最小绝对差

链接：https://leetcode.cn/problems/minimum-absolute-difference-in-bst/

直接按照中序遍历的顺序利用后者减去前者更新不同节点值之间的最小差值

 // 我们只要按照前序遍历然后逐个比较前后节点的差值就OK了，并用一个变量记住当前节点差的最小值
class Solution {
public:
    int res = INT_MAX; // 保证是中序遍历中的后面节点减去当前节点，所以-1其实是非法值，是一定会被更新的
    TreeNode *pre = NULL;
    void recursion(TreeNode *root)
    {
        if(root == NULL) return;
        // 开始的时候先向左递归
        recursion(root -> left);
        if(pre != NULL) res = min(res,root -> val - pre -> val);
        pre = root;

        recursion(root -> right);
    }
    int getMinimumDifference(TreeNode* root) {
        recursion(root);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Leecode 501.二叉搜索树中的众数

链接：https://leetcode.cn/problems/find-mode-in-binary-search-tree/

一看就是要用到容器。直观想法就是用哈希表对二叉树搜索一遍，然后对其中的元素进行处理

class Solution {
public:
    unordered_map<int,int> m;
    bool static cmp(const pair<int,int>& s1,const pair<int,int>& s2)
    {
        return s1.second > s2.second; // 对second也就是该数字出现的次数进行排序
    }  
    void recursion(TreeNode* root)
    {
        // 如果是空值就直接返回
        if(root == NULL) return;
        // 只要不是空值就直接记录，我们这里使用的是中序遍历，其实什么遍历顺序都是OK的
        m[root -> val]++;
        recursion(root -> left);
        recursion(root -> right);
    }
    vector<int> findMode(TreeNode* root) {
        // 首先把所有节点都加入到哈希表中，然后利用这个哈希表新创建一个vector
        // 然后对vector进行排序然后输出，这样其实并没有要求递归顺序
        recursion(root); 
        vector<pair<int,int>>vec (m.begin(),m.end()); // 注意vector是怎么接哈希表的

        vector<int> res;
        sort(vec.begin(),vec.end(),cmp);

        int number = vec[0].second;
        for(int i=0;i<vec.size();i++) 
        {
            if(vec[i].second == number) res.push_back(vec[i].first);
        }

        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

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

链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

注意一个细节：我们是如何处理最近公共祖先是p或者q的？

这里假设我们在遍历二叉树的时候先搜到了q，那么有两种情况：

1. p在q的子树上，也就是二者的最近公共祖先就是q
2. p不在q的子树上

显然不论哪种情况，我们都应该直接返回q，第一种情况对应着在q的父节点的另外一侧搜不到p；第二种情况对应着在q的下面继续搜索是无效的

那么显然，遇见q或者p我们就应该直接返回！

剩余情况是没有搜到q或者p，我们就应该继续递归当前节点的左右子树

那么应该如何return呢？

1. 如果左右节点都不为空，此时p和q分别在当前节点的左右子树上，所以应该返回root
2. else 如果左节点不为空返回左节点，else 如果右节点不为空返回右节点
3. else 直接返空值

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 看见题目给我们的函数的返回值就是指针，所以我们可以直接用
        if(root == NULL || root == p || root == q) return root;

        root -> left =  lowestCommonAncestor(root -> left,p,q);
        root -> right = lowestCommonAncestor(root -> right,p,q);

        if(root -> left != NULL && root -> right != NULL) return root ;
        if(root -> left != NULL) return root -> left;
        if(root -> right != NULL) return root -> right;
        return NULL;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/

还是返回公共祖先，但是环境是二叉搜索树，那么我们就能对上面的代码进行优化

1. 若当前节点的值同时大于p和q的值，那么我们就往其左子树搜索
2. 若当前节点的值同时小于p和q的值，那么我们就往其右子树搜索
3. 若当前节点的值恰好位于p和q中间，那么这个节点就是二者的最近公共祖先，因为不论是向左还是向右递归都会导致这个性质消失，而只有公共祖先才满足值位于左子树和右子树中间这个性质

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 看见当前函数的返回值就是指针，因此我们直接在这个函数上面写递归
        if(root == NULL) return root;
        
        if((root -> val > p->val && root -> val < q->val) || (root -> val < p->val && root -> val > q->val)) return root;

        if(root -> val > p->val && root -> val > q->val) {root -> left =  lowestCommonAncestor(root -> left,p,q); if(root -> left != NULL) return root -> left;}
        if(root -> val < p->val && root -> val < q->val) {root -> right = lowestCommonAncestor(root -> right,p,q);if(root -> right != NULL) return root -> right;}

        // 因为递归左右子树是选择性的，也就是说不一定去递归，那么我们在递归完毕后判断：若是没有返回空，那么我们就直接返回
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

这种写法其实还是有一些细节的。根据我们前面描述的，一共会有四种情况：当前节点是空节点；当前节点由于值位于p和q之间故一定是最近公共祖先；当前节点是p；当前节点是q

1. 首先判断当前节点是不是空节点，若是空节点直接返回空就完事了
2. 其次判断当前节点的值是不是位于q和p之间，若是，那么当前节点一定是最近公共祖先，直接返回就OK
3. 若不是，那么接下来看p和q是位于当前节点的左子树还是右子树上面，然后分情况递归
4. 若都不是，那么当前节点一定是p或q之一，直接返回当前节点就OK

为什么左节点有值或者右节点有值就一定可以返回呢？因为当前节点肯定不是最近公共祖先，才会去分别递归左右子树

按照这个逻辑，我们还可以进一步优化——如果当前节点就是最近公共祖先，那么一定不满足递归左右子树的条件，所以会直接return root，故我们其实也不需要判断当前节点的值是不是位于左右子树中间，简化代码如下：

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == NULL) return root;
        if(root -> val > p->val && root -> val > q->val) {root -> left =  lowestCommonAncestor(root -> left,p,q); if(root -> left != NULL) return root -> left;}
        if(root -> val < p->val && root -> val < q->val) {root -> right = lowestCommonAncestor(root -> right,p,q);if(root -> right != NULL) return root -> right;}
        return root;
    }
};
1
2
3
4
5
6
7
8
9

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

链接：https://leetcode.cn/problems/insert-into-a-binary-search-tree/

仔细分析题意我们意识到可以直接插入到叶子节点上面而不需要改变其他节点的结构

因为是二叉搜索树，所以我们是有方向地递归，所以递归到的空值都是符合题意的

那么我们直接递归就好了呀

但是如何处理递归的终止条件呢？因为若是当前节点为空，并不容易把握到当前节点的上一个节点是什么

因为插入一次就完事，所以我们考虑在递归之前就插入（若递归的目标是空），插入后就把flag置1

这样终止条件就是if(flag)，也就是插入完毕以后直接递归

所以递归函数也不要返回值

class Solution {
public:
    int flag = 0;
    void recursion(TreeNode* &root,int val)
    {
        if(flag) return;
        // 可以考虑先插入，后递归
        if(val > root -> val) {if(root -> right == NULL) {root -> right = new TreeNode(val);flag = 1;return;} recursion(root -> right,val);}
        if(val < root -> val) {if(root ->  left == NULL) {root -> left  = new TreeNode(val);flag = 1;return;} recursion(root -> left,val); } // 如果当前子节点不为空，那么就不能直接插入，我们继续递归        
    }
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        // 我们还是直接递归，但是返回值是指针吗？
        // 其实插入之后就不需要什么返回值了，因为是单步的操作，所以我们可以设置一个flag函数，插入完成后就设置成1，然后直接return就完事了
        if(root == NULL) {root = new TreeNode(val);return root;}
        recursion(root,val);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

链接：https://leetcode.cn/problems/delete-node-in-a-bst/

首先要把返回值给想好，返回值不合适题目就异常难做，然后就是考虑好所有情况，之后就蛮容易A的

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        // 首先我们要想好删除节点的所有情况
        // 最简单的情况就是要删除的节点是叶子节点，但是即使是最简单的情况，删除之后我们也要其父亲指向空而不能再指向这个被删除的节点
        // 很容易想到的一种想法就是维护当前节点的前面一个节点，但是这样很费劲，代码也特别难写，所以我们考虑直接让函数返回指针，然后我们递归调用当前的节点的左右子树
        // 这样删除之后左右子树向上return就可以直接把合法的节点返回给其父亲
        
        // 因为我们递归的时候没有判空，所以要把遇到空节点的情况写出来
        if(root == NULL) return NULL;
        // 先把删除叶子节点的情况给写出来
        if(root -> val == key)
        {
            if(root -> left == NULL && root -> right == NULL)
            {
                delete root;
                return NULL;
            }
            // 我们接着考虑删除节点的其他情况
            // 当前节点只有一条分支，也就是说当前节点只有左子树或者右子树
            else if(root -> left != NULL && root -> right == NULL)
            {
                TreeNode* cur = root->left;
                delete root;
                return cur;
            }
            else if(root -> right != NULL && root -> left == NULL)
            {
                TreeNode* cur = root->right;
                delete root;
                return cur;
            }
            // 此时左右节点都不为空，其实有两种拼接方式：把左儿子接上去然后把左儿子下面最大的节点的右侧接上当前节点的右儿子；或者是把右儿子接上去并且把右儿子下面最小的节点的左侧接上当前节点的左儿子，我们选择一种方法就可，这里选择第一种
            else
            {
                TreeNode* cur = root -> left;
                TreeNode* tar = cur;
                while(tar -> right!=NULL) tar = tar -> right;
                tar -> right = root -> right;
                delete root;
                return cur;
            }
        }
        // 如果当前节点不是目标节点，那么就朝合适的方向递归
        if(root -> val > key) root -> left =  deleteNode(root -> left, key);
        if(root -> val < key) root -> right = deleteNode(root -> right,key);
        // 因为题目要求返回头节点，所以直接返回头节点就OK
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

Leecode 669. 修剪二叉搜索树

链接：https://leetcode.cn/problems/trim-a-binary-search-tree/

此题和前面两题有明显的区别：之前两个题目都是删除一个节点，这个题目是删除“一些”节点

所以我们return的时机需要把握一下：

1. 刚开始的时候若是遇到了空节点，我们就直接return NULL
2. 接下来我们处理值不位于区间内的情况，其实和上一题很类似，删除的节点有很多种情况…但是我们不能直接返回当前节点，因为不能保证后面节点都符合题意，所以要return 递归函数

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        // 因为需要删除“一些节点”，所以我们返回值的时机需要改变
        // 那么是返回指针吗？修改节点之后返回指针是相对容易的做法
        if(root == NULL) return NULL;

        // 接下来看不合法情况的返回值
        if(root -> val > high || root -> val < low)
        { 
            if(root -> left == NULL && root -> right == NULL) return NULL;

            else if(root -> left != NULL && root -> right == NULL) return trimBST(root -> left, low,high);

            else if(root -> right != NULL && root -> left == NULL) return trimBST(root -> right,low,high);

            else
            {
                if(root -> val > high) return trimBST(root -> left,low,high);
                else return trimBST(root -> right,low,high);
            }

        }

        root -> left =  trimBST(root -> left,low,high);
        root -> right = trimBST(root -> right,low,high);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

但是我们中间的一大段逻辑其实都可以两行搞定

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {

        if(root == NULL) return NULL;
        
        if(root -> val > high)  return trimBST(root->left,low,high);
        if(root -> val < low)   return trimBST(root->right,low,high);

        root -> left  = trimBST(root->left,low,high);
        root -> right = trimBST(root ->right,low,high);

        return root ; 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

因为如果当前节点的值大于了high，那么右子树全都pass；同理如果当前的值小于low，那么左子树的值全都pass，也就是说我们直接返回递归就好，不需要考虑那么多复杂的情况

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

链接：https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/

这道题其实比之前做的“利用后序数组和中序数组构建二叉树”要简单很多

首先找到中间节点令其作为当前数组的根节点，然后划分数组左右递归建树就完事了

递归结束条件还是：当前数组为空

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        // 递归建树，找见中间节点后划分数组，然后分别递归
        if(nums.size() == 0) return NULL;
        int mid = (int)nums.size()/2;
        TreeNode* cur = new TreeNode(nums[mid]);

        // 开始划分数组
        vector<int> nums1 (nums.begin(),nums.begin() + mid);
        vector<int> nums2 (nums.begin() + mid + 1,nums.end());

        cur -> left = sortedArrayToBST(nums1);
        cur -> right = sortedArrayToBST(nums2);

        return cur;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Leecode 538. 把二叉搜索树转换为累加树

链接：https://leetcode.cn/problems/convert-bst-to-greater-tree/

这道题我首先想到的是返回值为int，尝试了一番发现很难做…

为什么难做？因为有返回值基本上就需要接住返回值

我们一般都是递归左子树和递归右子树吧，那么是根节点接住返回值吗？

if(root -> right != NULL) root ->  val += recursion(root->right); 
if(root -> left != NULL) root -> val += recursion(root->left); 
1
2

这样肯定是错的吧，照这样写中间节点的值反而是最大的，按照题意应该是左侧的节点值最大

所以我们需要重新思考返回值，也要开始思考遍历的顺序

右侧节点是最先开始遍历的，然后更新中间节点，然后更新中间节点的左子树…

所以遍历顺序其实是：右 -> 中 -> 左

要实现这种遍历顺序，我们就不能要返回值

我们用递归实现就简单很多

class Solution {
public:
    int sum = 0;
    void recursion(TreeNode* root)
    {
        if(root == NULL) return;
        // 先递归右侧
        recursion(root -> right);
        // 递归完毕之后往上return更新节点值
        sum += root -> val;
        root -> val = sum;
        // 如果当前节点有左子树，那么再遍历左子树
        recursion(root -> left);
    }
    TreeNode* convertBST(TreeNode* root) {
        int sum = 0;
        recursion(root);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

二叉树淦完了！欢呼~