[专业推!慎入]简单介绍深度搜索及其应用

发表于 算法 2017-03-22 阅读数: 141

最近刷LeetCode遇到了深度搜索(DFS),确实也是苦恼了一番。

深度搜索是一种用于遍历搜索树或者图的方法,它会尽可能深地搜索分支。当分支已经到达终点,它会返回上一个支点,搜索另一个分支。直到所有的节点都被成功搜索到才终止程序。搜索顺序如下。

深度搜索 讲解

由于其用途及其广泛,该算法的发明者获得了诺贝尔奖。

LeetCode上的原题目如下:

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).For example:Given binary tree [3,9,20,null,null,15,7],

深度搜索

return its bottom-up level order traversal as:

[

  [15,7],

  [9,20],

  [3]

]

什么意思呢?

输入一个二叉树,输出要按照层次输出,比如15和7最深,它们最先输出。9和20第二深,它们第二个输出,以此类推。

一开始拿到这个题目是毫无头绪的,但是一旦我们开始写代码,我们就会尝试记录每一层的数字,然后把层数和数字都保留下来。但是这样处理很麻烦,效率也不高。但我们能明确目标:记录深度和数字。

每次遇到节点就记录数字和层数,数字和层数放到哪里比较适合?当然是动态数组了!有什么算法是一层一层下去的?自然是递归了。递归的话我们要怎么创造动态数组和记录每一层层数?

首先我们能确定我们需要一个动态二维数组、一个根节点和深度。所以可以先造个vector和函数头

std::vector<std::vector<int> > ans;

void dfs(BitNode *root,int height){}

然后我们先解决基准状态:

if(root == NULL) return;

现在问题是怎么记录某个深度的数字呢?我们已经可以知道深度了(形参里有),那么我们就可以根据这个,往二维vector里放个vector(因为vector是需要人为初始化的,这里需要耐心理解)。

while (ans.size() <= height)

    ans.push_back(std::vector<int>());

这样我们就能把值放进去了。

ans[height].push_back(root->val);

然后递归即可,注意每一层都要让height + 1。

dfs(root->left, height + 1);

dfs(root->right, height + 1);

这样,最后递归回来的就是我们想要的层数及其数字。最后进行一点小处理就行。

完整代码已经在https://github.com/Ckend/GongZhongHao发布(看好是今天的)。

欢迎关注微信公众号:幻象客https://www.huanxiangke.com

欢迎进入极致分享:https://alltoshare.com

幻象客 二维码

Add comment