参数为二叉树和一个整数，求所有和为该整数的路径

LJ2016 的个人博客 / 0 / 0 / 创建于 5年前

javascript 虽然与PHP不同，写起简单的算法来也是简单有趣
题目，参数为二叉树和一个整数，求所有和为该整数的路径

典型的回溯法运用

function Node(value)
{
    this.value = value;
    this.left = this.right = null;
}

function find_path(root, value, path, paths)
{
    if(!root) return;
    path.push(root.value);
    if(root.value == value){
        console.log(path);
        paths.push([...path]);
    }

    find_path(root.left, value - root.value, path, paths);
    find_path(root.right, value - root.value, path, paths);
    path.pop(root.value);

    return paths;
}

function print_tree(root)
{
    let a = tree2array(root);
    console.log(a);
}

function tree2array(root, s = [])
{
    if(!root) return;
    tree2array(root.left, s);
    s.push(root.value);
    tree2array(root.right, s);
    return s;
}

let root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.right.right = new Node(-1);

left = root.left;
left.left = new Node(4);
left.right = new Node(-1);
left.right.left = new Node(1);

// print_tree(root);

let paths = find_path(root, 3, [], []);
console.log(paths);