算法搜索

树的层序遍历与BFS搜索

字数统计: 2.2k字   |   阅读时长: 10分
, , ,

摘要: 树的遍历与搜索，题目清单

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

$1 基础层序遍历

模板题

102. 二叉树的层序遍历

算法1：队列

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:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int> > result;
        if(root == nullptr) return result;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty())
        {
            vector<TreeNode*> level_treenodes;
            vector<int> level_items;
            while(!q.empty())
            {
                level_treenodes.push_back(q.front());
                q.pop();
            }
            for(TreeNode* treenode:level_treenodes)
            {
                level_items.push_back(treenode -> val);
                if(treenode -> left != nullptr)
                    q.push(treenode -> left);
                if(treenode -> right != nullptr)
                    q.push(treenode -> right);
            }
            result.push_back(level_items);
        }
        return result;
    }
};

算法2：递归

递归函数 _levelOrder 将层次的节点加入到 level_result，返回层次的节点个数。

1
int _levelOrder(TreeNode* node, vector<int>& level_result, int level);
1
2
3
4
5
6
7
根的 level 为 0
枚举 level, 从 0 开始:
    调用 _levelOrder(root,  level_result, level);
    调用时是从 root 开始的，不断向下递归，并 --level
    递归到 level == 0 则到了目标层次，处理该节点并返回 1(当前节点 node 代表的子树中的答案数)
    所有的递归调用都返回之后，返回总的答案数
直至枚举到某个 level，_levelOrder(root,  level_result, level); 调用返回 0，则 break 掉，停止枚举 level

注意：重复计算很多。

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
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int> > result;
        if(root == nullptr) return result;
        int level = 0;
        while(true)
        {
            result.push_back(vector<int>());
            if(_levelOrder(root, result[level], level) == 0)
            {
                if(result[level].empty())
                    result.pop_back();
                break;
            }
            ++level;
        }
        return result;
    }

private:
    int _levelOrder(TreeNode* root, vector<int>& level_result, int level)
    {
        if(!root || level < 0)
            return 0;
        if(level == 0)
        {
            level_result.push_back(root -> val);
            return 1;
        }
        return _levelOrder(root -> left, level_result, level - 1)
            + _levelOrder(root -> right, level_result, level - 1);
    }
};

算法3：双指针

1
2
指针1：指向访问当前层开始的点
指针2：指向当前层结束节点的下一位置

vector<TreeNode*> 的作用跟队列差不多，只是不用入队和出队实时更新当前层的节点范围，而是用双指针。

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
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int> > result;
        if(root == nullptr) return result;
        vector<TreeNode*> nodes;
        nodes.push_back(root);
        int cur = 0, end = 1;
        while(cur < (int)nodes.size()) // 随着更新，nodes 的 size 动态变化
        {
            result.push_back({});
            end = nodes.size();
            while(cur < end)
            {
                // 处理节点数据 nodes[cur] -> data
                result.back().push_back(nodes[cur] -> val);
                if(nodes[cur] -> left)
                    nodes.push_back(nodes[cur] -> left);
                if(nodes[cur] -> right)
                    nodes.push_back(nodes[cur] -> right);
                ++cur;
            }
        }
        return result;
    }
};

N 叉树的层序遍历

429. N叉树的层序遍历

变种层序遍历

基于层信息的搜索

垂序遍历

314. 二叉树的垂直遍历

给你一个二叉树的根结点，返回其结点按 垂直方向（从上到下，逐列）遍历的结果。

如果两个结点在同一行和列，那么顺序则为 从左到右。

提示：

1
2
树中结点的数目在范围 [0, 100] 内
-100 <= Node.val <= 100

示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[9],[3,15],[20],[7]]

示例 2：
输入：root = [3,9,8,4,0,1,7]
输出：[[4],[9],[3,0,1],[8],[7]]

示例 3：
输入：root = [3,9,8,4,0,1,7,null,null,null,2,5]
输出：[[4],[9,5],[3,0,1],[8,2],[7]]

算法：deque BFS

用 deque<vector<int> > result_deque(1, vector<int>()); 维护遍历过程中的中间结果。随着层加深，deque 中的各个列在层序遍历过程中更新答案。

如果当前层的最左节点有左子树，需要在 deque 左边加入新的一列 deq.push_front({})，如果当前层的最右节点有右子树，需要在 deque 右边加入新的一列 deq.push_back({})。

层序遍历时，进队的数据是 pair<TreeNode*, DQI>，一个节点对应一个指向 deque 中相应位置的 vector 的指针。

层序遍历在同一层天然从左往右，重合节点按照从左往右顺序这条要求自然满足。

代码 (C++)

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
class Solution {
public:
    vector<vector<int>> verticalOrder(TreeNode* root) {
        if(!root) return vector<vector<int> >();
        deque<vector<int> > result_deque(1, vector<int>());
        using DQI = deque<vector<int> >::iterator;

        DQI iter = result_deque.begin();
        queue<pair<TreeNode*, DQI> > q;
        q.push(pair<TreeNode*, DQI>(root, iter));

        vector<pair<TreeNode*, DQI> > level_nodes;
        while(!q.empty())
        {
            level_nodes.clear();
            while(!q.empty())
            {
                level_nodes.push_back(q.front());
                q.pop();
            }
            for(auto item: level_nodes)
            {
                TreeNode *node = item.first;
                DQI iter = item.second;
                iter -> push_back(node -> val);
                if(node -> left)
                {
                    if(iter == result_deque.begin())
                        result_deque.push_front(vector<int>());
                    --iter;
                    q.push(pair<TreeNode*, DQI>(node -> left, iter));
                    ++iter;
                }
                if(node -> right)
                {
                    ++iter;
                    if(iter == result_deque.end())
                        result_deque.push_back(vector<int>());
                    q.push(pair<TreeNode*, DQI>(node -> right, iter));
                    --iter;
                }
            }
        }

        vector<vector<int> > result;
        for(vector<int> item: result_deque)
            result.push_back(item);
        return result;
    }
};

987. 二叉树的垂序遍历

给你二叉树的根结点 root ，请你设计算法计算二叉树的 垂序遍历 序列。

对位于 (row, col) 的每个结点而言，其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。树的根结点位于 (0, 0) 。

二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点，则按结点的值从小到大进行排序。

返回二叉树的 垂序遍历 序列。

示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[9],[3,15],[20],[7]]
解释：
列 -1 ：只有结点 9 在此列中。
列 0 ：只有结点 3 和 15 在此列中，按从上到下顺序。
列 1 ：只有结点 20 在此列中。
列 2 ：只有结点 7 在此列中。

示例 2：
输入：root = [1,2,3,4,5,6,7]
输出：[[4],[2],[1,5,6],[3],[7]]
解释：
列 -2 ：只有结点 4 在此列中。
列 -1 ：只有结点 2 在此列中。
列 0 ：结点 1 、5 和 6 都在此列中。
1 在上面，所以它出现在前面。
5 和 6 位置都是 (2, 0) ，所以按值从小到大排序，5 在 6 的前面。
列 1 ：只有结点 3 在此列中。
列 2 ：只有结点 7 在此列中。

示例 3：
输入：root = [1,2,3,4,6,5,7]
输出：[[4],[2],[1,5,6],[3],[7]]
解释：
这个示例实际上与示例 2 完全相同，只是结点 5 和 6 在树中的位置发生了交换。
因为 5 和 6 的位置仍然相同，所以答案保持不变，仍然按值从小到大排序。

提示：

1
2
树中结点数目总数在范围 [1, 1000] 内
0 <= Node.val <= 1000

算法：deque BFS

层序遍历过程进队的数据，以及维护答案的数据结构(deque)与 314. 二叉树的垂直遍历 一样。 但难点在于多条线在同一点相交的时候，需要按照节点值排序输出。

层序遍历天然的从左到右不再满足，需要一个排序机制：当 DQI = deque<vector<int> >::iterator (队列中与 TreeNode* 对应的另一个字段)相同的时候，按照树节点的权值排序。将队列中的数据 (TreeNode*, DQI) 包装成 PDT，整体进行排序。见代码。

1
2
3
4
5
6
7
8
9
10
11
12
using DQI = deque<vector<int> >::iterator;
using PDT = pair<DQI, TreeNode*>;

struct Cmp
{
    bool operator()(const PDT& pdt1, const PDT& pdt2)
    {
        if(pdt1.first == pdt2.first)
            return (pdt1.second -> val < pdt2.second -> val);
        return pdt1.first < pdt2.first;
    }
};

代码 (C++)

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
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        if(!root) return vector<vector<int> >();
        deque<vector<int> > result_deque(1, vector<int>());
        queue<PDT> q;
        q.push(PDT(result_deque.begin(), root));
        vector<PDT> level_nodes;
        while(!q.empty())
        {
            level_nodes.clear();
            while(!q.empty())
            {
                level_nodes.push_back(q.front());
                q.pop();
            }
            int n = level_nodes.size();
            sort(level_nodes.begin(), level_nodes.end(), Cmp());
            for(int i = 0; i < n; ++i)
            {
                auto item = level_nodes[i];
                DQI iter = item.first;
                TreeNode *node = item.second;
                iter -> push_back(node -> val);
                if(node -> left)
                {
                    if(iter == result_deque.begin())
                        result_deque.push_front(vector<int>());
                    --iter;
                    q.push(PDT(iter, node -> left));
                    ++iter;
                }
                if(node -> right)
                {
                    ++iter;
                    if(iter == result_deque.end())
                        result_deque.push_back(vector<int>());
                    q.push(PDT(iter, node -> right));
                    --iter;
                }
            }
        }
        vector<vector<int> > result;
        for(vector<int> item: result_deque)
            result.push_back(item);
        return result;
    }

private:
    using DQI = deque<vector<int> >::iterator;
    using PDT = pair<DQI, TreeNode*>;

    struct Cmp
    {
        bool operator()(const PDT& pdt1, const PDT& pdt2)
        {
            if(pdt1.first == pdt2.first)
                return (pdt1.second -> val < pdt2.second -> val);
            return pdt1.first < pdt2.first;
        }
    };
};
Share