何为深度搜索

image.png
如上图 假如进入深度搜索
搜索顺序为
A — C — F — G —B — D — E
也就时将左子树搜索完成后没有发现目标值再去搜索右子树
代码实现二叉树的深度优先搜索

  1. class Node {
  2.     constructor(value) {
  3.         this.value = value;
  4.         this.left = null;
  5.         this.right = null;
  6.     }
  7. }
  9. let a = new Node("a")
  10. let b = new Node("b")
  11. let c = new Node("c")
  12. let d = new Node("d")
  13. let e = new Node("e")
  14. let f = new Node("f")
  15. let g = new Node("g")
  16. a.left = c;
  17. c.left = f;
  18. b.left = d;
  19. a.right = b;
  20. b.right = e;
  21. c.right = g;
  23. /**
  24.  * 二叉树深度优先搜索
  25.  * @param {*} root    开始值//根节点
  26.  * @param {*} target  目标值
  27.  * @returns
  28.  */
  29. function f1(root , target){
  30.     if(root == null || target == null ) return false;
  31.     if(root.value == target){
  32.         return true;
  33.     }
  34.     var left = f1(root.left,target);
  35.     var right = f1(root.right,target);
  36.     return left || right;
  37. }
  39. console.log(f1(a,"o"))