二叉树的搜索

深度优先搜索： 更适合探索未知

广度优先搜索： 更适合探索局域

/* 深度优先搜索： */
function Node(value) {
    this.value = value;
    this.left = null;
    this.right = null;
}

let a = new Node('a');
let b = new Node('b');
let c = new Node('c');
let d = new Node('d');
let e = new Node('e');
let f = new Node('f');
let g = new Node('g');

a.left = c;
a.right = b;
c.left = f;
c.right = g;
b.left = d;
b.right = e;


// 对于二叉树来说，深度优先搜索，和前序遍历的顺序是一样的
function deepSearch(root, target) {
    if (root == null || target == null) {
        return false;
    }
    if (root.value == target) {
        return true;
    }
    let left = deepSearch(root.left, target);
    let right = deepSearch(root.right, target);
    return left || right;
}

console.log(deepSearch(a, 'h'));

/* 广度优先搜索 */
function Node(value) {
    this.value = value;
    this.left = null;
    this.right = null;
}

let a = new Node('a');
let b = new Node('b');
let c = new Node('c');
let d = new Node('d');
let e = new Node('e');
let f = new Node('f');
let g = new Node('g');

a.left = c;
a.right = b;
c.left = f;
c.right = g;
b.left = d;
b.right = e;

function f2(rootList, target) {
    if (rootList == null || rootList.length == 0 || target == null) {
        return false;
    }
    let childList = []; //当前层所有节点的子节点，都在这个list中，这样传入下一层级的时候，就可以遍历整个层级的节点。
    for (let i = 0; i < rootList.length; i++) {
        if (rootList[i] == null) {
            return false;
        }
        if (rootList[i] != null && rootList[i].value == target) {
            return true;
        } else {
            childList.push(rootList[i].left);
            childList.push(rootList[i].right);
        }
    }
    return f2(childList, target);
}


console.log(f2([a], 'd'));