深度优先搜索
- 实际应用
- 具体例子

深度优先搜索

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

实际应用

具体例子

1. 平衡二叉树（剑指Offer-55）

解法一：自底而上

var isBalanced = function(root) {
  return DFS(root) !== -1
};
function DFS(root) {
  if (!root) return 0
  let leftDeep = DFS(root.left)
  if (leftDeep === -1) return -1
  let rightDeep = DFS(root.right)
  if (rightDeep === -1 || Math.abs(leftDeep - rightDeep) > 1) return -1
  return Math.max(leftDeep, rightDeep) + 1
}

解法二：自顶向下

var isBalanced = function(root) {
  if (!root) return true
  let left = getHeight(root.left)
  let right = getHeight(root.right)
  if(Math.abs(left- right) > 1) {
    return false
  }
  return isBalanced(root.left) && isBalanced(root.right)
};
function getHeight(root) {
  if (!root) return 0
  let leftDeep = getHeight(root.left)
  let rightDeep = getHeight(root.right)
  return Math.max(leftDeep, rightDeep) + 1
}

2. 叶子相似的树（LeetCode-872）

解法：**

var leafSimilar = function(root1, root2) {
  let arr1 = [], arr2 = []
  DFS(root1, arr1)
  DFS(root2, arr2)
  return arr1.join() === arr2.join()
};
function DFS(root, ans) {
  if (!root.left && !root.right) ans.push(root.val)
  if (root.left) DFS(root.left, ans)
  if (root.right) DFS(root.right, ans)
}

3. N叉树的最大深度（LeetCode-559）

解法一：DFS递归

var maxDepth = function(root) {
  return DFS(root)
};
function DFS(root) {
  if (!root) return 0
  let count = 1
  root.children.forEach((item) => {
    count = Math.max(count, DFS(item) + 1)
  })
  return count 
}

解法二：迭代

var maxDepth = function(root) {
  if (!root) return 0
  if (!root.children) return 1

  var stack = [{
    node: root,
    deep: 1
  }]
  var depth = 0
  while(stack.length) {
    var item = stack.pop()
    if (!item) return
    var node = item.node
    var prevDeep = item.deep
    depth = Math.max(prevDeep, depth)
    for (var i = node.children.length - 1; i >= 0; i --) {
      stack.push({
        node: node.children[i],
        deep: prevDeep + 1
      })
    }
  }
  return depth
}

4. 路径总和

解法一：

var hasPathSum = function(root, sum) {
  let flag = false
  DFS(root, sum)
  function DFS(root, sum) {
    if (!root || flag) return 
    if (sum - root.val === 0 && !root.left && !root.right) return flag = true
    DFS(root.left, sum - root.val)
    DFS(root.right, sum - root.val)
  }
  return flag
};

// 更简写法
var hasPathSum = function(root, sum) {
 if (!root) return false
 if (!root.left && !root.right) {
   return sum === root.val
 }
 sum = sum - root.val
 return hasPathSum(root.left, sum) || hasPathSum(root.right, sum)
};

5. 相同的树（LeetCode-100）

解法一：

var isSameTree = function(p, q) {
  let pArr = DFS(p, [])
  let qArr = DFS(q, [])
  return qArr.toString() === pArr.toString()
};
function DFS(root, ans) {
  if (!root) return ans.push(null)
  ans.push(root.val)
  DFS(root.left, ans)
  DFS(root.right, ans)
  return ans
}


// 简化版
var isSameTree = function(p, q) {
  if (!p && !q) return true;
  if (!p || !q) return false;
  if (p.val !== q.val) return false;
  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

6. 颜色填充（LeetCode-面试题 08.10）

解法一：

var floodFill = function(image, sr, sc, newColor) {
  const len1 = image.length
  const len2 = image[sr].length
  const originColor = image[sr][sc]
 function DFS(x, y) {
   // 避免原数字和新数字相同
   if (x < 0 || y < 0 || x >= len1 || y >= len2 || image[x][y] !== originColor || image[x][y] === newColor) return ''
    image[x][y] = newColor
    DFS(x + 1, y)
    DFS(x - 1, y)
    DFS(x, y + 1)
    DFS(x, y - 1)
 }
 DFS(sr, sc)
  return image
};

7. 二叉树的所有路径（LeetCode-257）

解法一：

var binaryTreePaths = function(root) {
  const ans = []
  function DFS(root, result) {
    result = result.concat(root.val)
    if (!root.left && !root.right) {
      ans.push(result.join('->'))
      return 
    }
    root.left && DFS(root.left, result)
    root.right && DFS(root.right, result)
  }
  root && DFS(root, [])
  return ans
};

8. 二叉树的最大深度

解法一：DFS

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
  if (!root) return 0
  if (!root.left && !root.right) return 1
  let left = root.left ? maxDepth(root.left) : 0
  let right = root.right ? maxDepth(root.right) : 0
  return Math.max(left, right) + 1
};

解法二：BFS

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
  if (!root) return 0
  const stack = []
  let deep = 0
  stack.push({
    tree: root,
    deep: 1
  })
  while(stack.length) {
    let item = stack.shift()
    deep = item.deep
    item.tree.left && stack.push({
      tree: item.tree.left,
      deep: item.deep + 1
    })
    item.tree.right && stack.push({
      tree: item.tree.right,
      deep: item.deep + 1
    })
  }
  return deep
};

9. 对称二叉树（LeetCode-101）

解法一：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
  if (!root) return true
  let flag = true
  const left = DFS(root.left, 'left')
  const right = DFS(root.right)
  return left.toString() === right.toString()
};
function DFS(root, dic) {
  if (!root) return [null]
  let ans = []
  ans.push(root.val)
  if (dic === 'left') {
    ans.push(...DFS(root.left, dic))
    ans.push(...DFS(root.right, dic))
  } else {
    ans.push(...DFS(root.right, dic))
    ans.push(...DFS(root.left, dic))
  }
  return ans
}

// 更简写法
var isSymmetric = function(root) {
  return checkTree(root, root)
};
function checkTree(root1, root2) {
  if (!root1 && !root2) return true
  if (!root1 || !root2) return false
  return root1.val === root2.val && checkTree(root1.left, root2.right) && checkTree(root1.right, root2.left)
}

10. 递增顺序查找树（LeetCode-897）

解法一：生成新树

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var increasingBST = function(root) {
  let ans = current = null
  DFS(root)
  function DFS(root) {
    if (!root) return
    root.left && DFS(root.left)
    if (!ans) {
      ans = new TreeNode(root.val)
      current = ans
    } else {
      current.right = new TreeNode(root.val)
      current = current.right
    }
    root.right && DFS(root.right)
  } 
  return ans
};

解法二：更改树的连接方式

var increasingBST = function(root) {
  let ans = current = null
  ans = new TreeNode(0)
  current = ans
  inorder(root)
  function inorder(node) {
    if (!node) return
    inorder(node.left)
    node.left = null
    current.right = node
    current = node
    inorder(node.right)
  }
  return ans.right
};