0%

相关的编程题汇总-树

发表于 更新于 分类于 ，

汇总了刷题中遇到的 树 相关的题目，例如二叉树的遍历，公共祖先问题等

二叉树

特定深度节点链表

​ 1598931882407

这个题 使用 层序遍历的 即可简单完成。类似于广度优先搜索的策略。只不过这里为了体现层的 特点，不是直接将 节点 传入队列 遍历，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<ListNode*> listOfDepth(TreeNode* tree) {
        if(tree==nullptr)return vector<ListNode*>();
        vector<ListNode*> v;
        queue<TreeNode*> q;
        q.push(tree);
        while(!q.empty()){
            ListNode *h = new ListNode();
            ListNode *k=h;
            for(int i=q.size(); i>0; i--){    /// 这里 先把size 赋给 i 即便for循环内改变了 队列的大小，最终也只是for遍历了原先的元素 ，所有可以记录 遍历的深度
                TreeNode *p = q.front();
                q.pop();
                k->next = new ListNode(p->val);
                k = k->next;
                if(p->left)q.push(p->left);
                if(p->right)q.push(p->right);
            }
            v.push_back(h->next); 
        }
        return v;
    }
};

合法二叉搜索树

最简单的思路就是 中序遍历 打印出二叉树所有的值，然后判断是不是递增的就可。必须是中序遍历才能将标准的搜索树递增的顺序打印出来。

树的子结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool helper(TreeNode* A, TreeNode* B) {
        if (A == NULL || B == NULL) {
            return B == NULL ? true : false;
        }
        if (A->val != B->val) {
            return false;
        }
        return helper(A->left, B->left) && helper(A->right, B->right);
    }
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if (A == NULL || B == NULL) {
            return false;
        }
        return helper(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);
    }
};

​ 这道题的思路是，双递归。首先 isSubStructure 第一个递归用来对A树递归，在A中搜索和B树的根节点 相同的 子节点 即return 中的 helper(A, B) 若该节点不满足则递归A 分别搜索A 的左右子节点是否满足。 而help函数的递归是在 第一个输入子节点A,B val值相同时，才开启递归，A和B分别往左右 递归去判断后面的节点是否相同。也就是此时二者的递归是同步的。注意helper中 若B是NULL 那位对应位置的A可以是任意值，所以直接返回True。

翻转二叉树以匹配先序遍历

​ 这道题容易理解错。题目的翻转的意思不是交换左右子节点的位置，它的反转是交换先序遍历中 左右子节点的访问顺序，之后能否匹配上给定的行程。因此解题思路是 首先 还是先序遍历，如果当前节点值 和 期待的行程值不一样直接返回false；接着先序遍历会递归访问左子节点 再右子节点。但是，这里在访问左子节点时要先判断下如果左子节点非空 且 值等于期待的行程的值 那么再递归的访问左右子节点，否则看右子节点值与期待的是否一样，若是，则先递归右子节点再左子节点，这就是所谓的交换子节点了。

收集树上所有苹果

​ 这道题主要思路 是 从苹果往它上方通往根节点0的方向回退，并将总路程+2(该节点到父节点的往返) 这样对于有公共父节点的苹果，只用计算父节点到 根节点0的距离 和 各个苹果到该节点的距离。 首先利用并查集里的方法 构建一个 parent 的一维数组，parent[0] = 0代表起始的根节点，后面paent[1] = 0 表示节点1 的父节点是0，类似的 每个节点与它直系的可以通往 节点 0 的父节点相接。这个parent数组的初始化方法是：在并查集合并节点时，首先判断两个节点p,q的迭代到最后的根节点是不是0，若节点p的根节点不是0，q是，则 parent [p] = q 。初始化完了之后，将有苹果的节点加入队列，挨个访问，除了根节点之外 其余的在总路径上加2 表示往返 若他的父节点 没被访问过，则将它的父节点加入队列。

输出二叉树

​ 这道题的主要思路是 首先深度优先搜索确定 树的最大深度。这样就可以直到 最终输出数组的宽度和长度，然后再用递归写一个深度优先搜索来，来依次填数。而这里的填充方法 用二分法定位每个节点子节点在数组中的位置比较方便。

二叉树减树枝

​ 这道题思路很简单。写一个 dfs 后续遍历，如果递归左边和右边输出的树指针为NULL 且 当前节点 值为0 则返回NULL指针，否则直接返回 输入的结点。

二叉树右视图

​ 使用层次遍历，较简单。每次先把右子节点加入队列，每次输出只输出第一个节点的值。即可

重建二叉树

​ 这类题目有 从前序和中序遍历的结果生成二叉树，或者从前序和后续遍历的结果生成二叉树，中序后序遍历的结果生成二叉树。要根据 不同遍历的 特点来构造递归。

  • 前序遍历：根节点 + 左子树所有节点 + 右子树所有节点的值

  • 中序遍历：左子树的所有节点 + 根节点 + 右子树所有节点的值

  • 后续遍历：左子树的所有节点 + 右子树所有节点的值 + 根节点

    有了上述的规律，考虑 已知前序 和 后序遍历时，首先根节点 确定，然后根据前序遍历的 左子树序列的第一个值，即左子树的根节点值，在后续遍历序列中确定 左子树的范围。因为 前序和后续的同一颗子树的根节点 必然一个在最开始 一个在最结尾。这样递归的划分子树，构建即可。为了加快速度，使用Hash表构建 值->位置的索引，快速划分子树。

二叉树最近公共祖先

​ 这道题目的思想 在于 在一颗子树下的两个 待寻找的节点，找到最上面那个节点后 直接返回该节点，不用再往下递归搜索啦。因为如果深度往下搜的时候已经找到了 那么另一个要么 在它之下，要么在另一颗子树，这两种情况 最后最近的公共节点都是 这个返回的值。

二叉树中的最大路径和

思路比较简单，但是是个困难的题目

完全二叉树的节点个数

这个利用了 满二叉树的 性质。对于满二叉树 它的叶子节点的编号和路径是有规律的 。因此 先找到最左边的叶子节点，那么最底层的叶子节点的个数就是个范围，然后用二分搜索去确定最下面的叶子节点的具体编号。

字典序的第K小数字

完全十叉树，和满二叉树类似。主要是要熟悉完全二叉树的性质。

堆

无序数组的topK小元素

​ 可以使用优先队（大根堆），c++ 中的数据结构为priority_queue。思路是，首先对数组前K个元素建大根堆，然后依次读取数组后面的元素，若该元素大于 堆顶的元素，则丢弃不管，若小于堆顶元素，则将它入堆，并pop掉原本的根节点的数据。遍历完数组后，最后堆中剩下的就是TopK小的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector<int>vec(k, 0);
        if (k == 0) return vec; // 排除 0 的情况
        priority_queue<int>Q;
        for (int i = 0; i < k; ++i) Q.push(arr[i]);
        for (int i = k; i < (int)arr.size(); ++i) {
            if (Q.top() > arr[i]) {
                Q.pop();
                Q.push(arr[i]);
            }
        }
        for (int i = 0; i < k; ++i) {
            vec[i] = Q.top();
            Q.pop();
        }
        return vec;
    }
};

数据流的中位数

使用大小堆解决。一个大顶堆一个小顶堆。每次先把数据从小顶堆输入，输出到大顶堆。这样就保证了 小顶堆中的数始终大于等于大顶堆的数。（因为大顶堆的数是从小顶堆过来的，小顶堆弹出的一定是最堆中最小的，而大顶堆堆定数最大 ）最后每次维持小顶堆的数据量大于或等大顶堆中的数据量即可（如果大顶堆数量大于小顶堆数量，就反过来将大顶堆数据弹出一个给小顶堆，这样两堆元素数量就相等了）。这样当数据量为偶数时就是两个堆定元素平均，否则就是小顶堆的堆顶元素。

重构字符串

这个题很容易能想到用堆做

接雨水 II

同类题 一维的接雨水 （接雨水），这个是二维的 太变态了。但是基本原理都是用短板效应。每次找最短的板。 对于一维的接雨水，想象从上往下倒水，水只能从两边流出，因此取两边中的短边作为短板，然后不断往中间搜索，如果中间的比两边的短，那么这个就可以和短板构成一个接水槽，如果它比短板高，那么它不能作为接水槽，因为会往外流，但是可以更新边界的高度。使用双指针就可以完成整个逻辑。但是一维接雨水最好想的思路是，计算每个位置的板左边和右边最大的高度即可，但是这个最大高度其实不用每次都暴力搜索，只需要两次遍历，即可找到每个位置左边和右边的最大值。

同理对于二维的接雨水问题，中间能接多少水，取决于四周板最短的一块，但是不能暴力搜索最短的啊，直接使用小顶堆来动态维护最短边界。具体的思路。解题

比如说外围一圈，那个最短的地方肯定能结算它四周的位置，因为雨下的足够大，你不可能会低于这个短板，高于这个短板又会溢出，所以这个结算肯定是正确的。欸，这样的话，我每次都找外围的短板，然后结算它四周的位置，不断的缩小这个外围不就能把水量算出来了嘛！！！等等，短板用一次就丢好么？如果这个短板比中间所有的位置都要高，那你这圈就是再咋缩短板也不能变呀。所以短板得有个淘汰机制，什么情况下短板就没用了，那肯定你此时结算的圈的短板比之前的短板要高的时候了，我当前圈的短板更高，那我这个圈里的水都给我hold住了，不可能从之前的短板里溜出去了。

1.外围不断在变化，咋样能快速知道每次的短板是哪个呢？很明显用小根堆可以解决。 2.如何确保一个位置不被重复结算？用set？反正肯定最后所有位置都被结算一次，直接用个boolean数组就好了 3.然后再整个变量存一下此时短板的高度 4.堆里存的是当前外圈的板子，那么需要存那些信息呢？我要知道你多高，height跑不掉，我需要结算你四周的水量，所以你的位置也得知道，所以加上(row,col)

其他树

最多 K 次交换相邻数位后得到的最小整数

树状数组解决