深度优先搜索（DFS）+广度优先搜索（BFS）

问题背景描述

DFS与BFS，问题背景都是在树/图/状态集中寻找特定节点，两者不同之处在于针对搜索路径扩展的策略

BFS

所谓BFS，全称广度优先搜索，即遍历时优先考虑路径的广度，先将同级（深度相同）节点遍历完，再遍历下一级深度的节点

BFS比较符合人一般的思维模式，在算法实现上，通常是从根节点开始，把各节点顺序放入队列中，再对队列元素进行遍历代码模板：

def BFS(graph, start, end):
    queue = []
    queue.append([start])
    visited.add(start)

    while queue:
        node = queue.pop()
        visited.add(node)

        process(node)
        nodes = generate_related_nodes(node)
        queue.push(nodes)
    # other processing work

DFS

所谓DFS，全称深度优先搜索，即遍历时优先考虑路径的深度，先将同“枝”节点遍历完，再返回遍历其他“枝”的节点

相比于BFS，DFS则更契合于计算机的遍历“习惯”，计算机原生语言常使用类似于栈的结构，层层搜索。与树的遍历不同的是，图中有可能会出现环状结构，遍历时注意记录已访问的节点

DFS——递归方式代码模板：（较常用）

visited = set ()
    def dfs (node, visited):
        visited.add(node)
            # process current node here.
        ……    
        for next_node in node.children( ):
            if not next_node in visited:
                dfs(next_node, visited)

DFS——非递归方式代码模板：（不常用）

def DFS(self, tree):
    if tree.root is None:
        return []
    visited, stack = [], [tree.root]

    while stack:
    node = stack.pop()
    visited.add(node)

    process(node)
    nodes = generate_related_nodes(node)
    stack.push(nodes)
    # other processing work

如果说BFS是先大致掌握各个领域基础知识，再慢慢深入了解，那么DFS就像是先精通一个领域，再往其他领域扩展

实战题目

二叉树层次遍历
输入：树的根节点，输出：一个数组，每层的节点作为其子数组

思路一：BFS，从上到下，每层遍历完再遍历下一层。如何判断当前节点是当前层最后一个节点：①把层级的信息加到输入参数中/②batch processing

Python版：

def levelOrder( self, root):
if not root: returR []
   result = []
queue = collections.deque()
queue.append(root) #visited = set(root)#树中不存在闭环问题，所以无需标记是否访问
while queue:
   level_size = len(queue)
   current_level = []

   for _ in range(level_size):
       node = queue.popleft()
       current_level.append(node.val)
       if node.left: 
           queue.append(node.left)#下一层子节点加入，这一层还不会处理
       if node.right: 
           queue.append(node.right)
   result.append( current_level)
return result

Java版：

public List<List<Integer>> levelOrder(TreeNode root){
List<List<Integer>> res = new ArrayList<>();
if (root == null)
   return res;
Queue<TreeNode> q = new LinkedList<>();
q.add ( root);

while( !q.isEmpty()){
   int levelSize = q.size();
   List<Integer> currLevel = new ArrayList<>();

   for(int i = 0; i < levelSize; i++){
       TreeNode currNode = q.poll();
       currLevel.add(currNode.val);

       if (currNode.left != null){
           q.add(currNode.left);
       }

       if (currNode.right != null){
           q.add(currNode.right);
       }
   }
   res.add ( currLevel);
}
return res;
}

思路二：DFS，先生成一个大数组，里面若干小数组置空表示各层元素。将一条分支的节点全部遍历完并填到小数组里，再遍历其他分支

def level0rder(self, root):
if not root:
   return []
self.result = []
self._dfs(root,0)
return self.result
def _dfs(self,node,level):
if not node: 
   return
if len(self.result) < level + 1:
   self.result.append([])

self.result[level].append(node.val)

self._dfs(node.left,level + 1)
self._dfs(node.right,level + 1)

二叉树最大深度与二叉树最小深度

思路一：递归查找左子树深度llen和右子树深度rlen，则最大深度即为max(llen+1,1,rlen)，最小深度同理

最大深度python版：

def maxDepth(self, root):
if not root: 
   return 0
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

最大深度java版：

return root ==null ? 0:
1 + Math.max(maxDepth(root.left),maxDepth(root.right))

最小深度java版注意左右子树都为空时，min(left,right)表达式非法不能直接求最小深度：

class Solution {
public:
int minDepth(TreeNode *root) {
   if(!root) return 0;
   if(!root->left) return 1 + minDepth(root->right);
   if(!root->right) return 1 + minDepth(root->left);
   // divide and conquer

   int leftMinDepth = minDepth(root->left);
   int rightMinDepth = minDepth(root->right);
   // process subproblems' results
   int result = 1+min(leftMinDepth,rightMinDepth);
   return result;
}
};

最小深度Java版另一种写法：

public class Solution {
public int minDepth(TreeNode root) {
 if( root == null) return 0;
 int left = minDepth( root.left);
 int right = minDepth( root.right);
 return ( left == 0 || right == 0)
 ?left + right + 1
 :Math.min(left, right) + 1;
}
}

思路二：BFS，按层扫描树的节点，每一层判断是否为叶子结点，若为叶子结点则记录深度，第一个叶子结点对应最小深度，最后一个叶子结点对应最大深度。时间复杂度O(N),N表示树的节点数
思路三：DFS，按分支遍历，随遍历记录层级，当遍历到叶子结点时记录深度，随遍历更新最大深度和最小深度。时间复杂度O(N)

有效括号生成

思路一：数学归纳法，先生成n=1的情况，后面一步一步扩展

思路二：递归发，n个括号对就有2n个字符，时间复杂度O(2²ⁿ)

def generateParenthesis(self, n):
self.list = []
self._gen(0, 0, n,"")return self.list
def _gen( self, left, right, n,result):
if left == n and right == n:
   self.list.append(result)
   return
if left < n:
   self._gen(left + 1,right,n, result +"(")
if left > right and right < n:
   self._gen(left, right + 1, n, result + ")")

思路三：在思路二的基础上进行改进，若局部不合法则不再递归，同时记录已使用的左、右括号

public List<String> generateParenthesis(int n) {
List<String= result = new ArrayList<String>();
generateOneByOne("",result, n, n);
return result;
}
public void generateOneByOne(String sublist, List<String> result,int left,int right){
if ( left == 0 && right =0){
   result.add ( sublist);
   return;
}
if (left>0{
   generateOneByOne(sublist +"(" , result,left-1,right);
}
if (right>left){
   generateOneByOne(sublist +")" , result, left,right - 1);
}
}

深度优先搜索与广度优先搜索

深度优先搜索（DFS）+广度优先搜索（BFS）

问题背景描述

BFS

DFS

实战题目

results matching ""

No results matching ""