Skip to content

Latest commit

 

History

History
191 lines (153 loc) · 5.98 KB

算法-深度优先算法.md

File metadata and controls

191 lines (153 loc) · 5.98 KB

前言

在没有正式开始算法学习之前，我就写过一篇目录树的广度优先遍历和深度优先遍历，今次系统学习下深度优先算法（DFS）。

深度优先搜索

深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。

深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。

实现方法

  1. 首先将根节点放入stack中。
  2. 从stack中取出第一个节点，并检验它是否为目标。
    1. 如果找到目标，则结束搜寻并回传结果。
    2. 否则将它某一个尚未检验过的直接子节点加入stack中。
  3. 重复步骤2。
  4. 如果不存在未检测过的直接子节点。
    1. 将上一级节点加入stack中。
    2. 重复步骤2。
  5. 重复步骤4。
  6. 若stack为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。

我在没有系统学习算法之前，往往青睐用递归解决问题。其实递归是很耗资源的方式，如果递归是将大问题分解为小问题，则完全可以用动态规划替代。而动态规划占用的空间往往是线性的。

1.相同的数（leetcode.100）

给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1:

输入:       1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

输出: true
示例 2:

输入:      1          1
          /           \
         2             2

        [1,2],     [1,null,2]

输出: false
示例 3:

输入:       1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

输出: false

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
  let stack1 = [p]
  let stack2 = [q]
  while (stack1.length > 0) {
    let first1 = stack1.shift()
    let first2 = stack2.shift()
    if (first1 && first2 && first1.val == first2.val) {
      stack1.unshift(first1.left,first1.right)
      stack2.unshift(first2.left,first2.right)
    } else if (first1 !== null || first2 !== null){
      return false
    }
  }
  return true
}

以上是我提交通过的解法，完全依照维基百科上的实现方法，不采用递归。

2.对称二叉树（leetcode.101）

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3


var isSymmetric = function(root) {
  if(root==null)return true
  let stack = [root.left,root.right]
  while (stack.length > 0) {
    let left = stack.shift()
    let right = stack.pop()
    if (left && right && left.val == right.val) {
      stack.unshift(left.left,left.right)
      stack.push(right.left, right.right)
    } else if (left !== null || right !== null) {
        return false
    }
  }
  return true
}

思路和上一道题是一样的，注意迭代的顺序就可以了。

3.路径综合（leetcode.112）

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例: 
给定如下二叉树，以及目标和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {boolean}
 */
var hasPathSum = function(root, sum) {
    if(root==null)return false
    root.sum=root.val
    let stack=[root]
    while(stack.length>0){
        let first=stack.shift()
         if(first.right){
            first.right.sum=first.sum+first.right.val
            stack.unshift(first.right)
        }
        if(first.left){
            first.left.sum=first.sum+first.left.val
            stack.unshift(first.left)
        }
        if(!first.right&&!first.left&&first.sum==sum)return true
    }
    return false
};

这道题有一点不一样，在遍历到当前节点时，需要先判断是否有子节点，为子节点提前设置总和值，因为迭代之后会丢失父节点的信息。