javascript - 有缺陷的二叉树

Question

我正在尝试解决 codeforces 737A使用 javascript，它正在对 2*x 和 10*x+1 树进行二分搜索，从给定的输入 a 到另一个输入b，但是我的程序似乎只能搜索2*x处的那些节点，而那些10*x+1似乎被忽略。有趣，为什么？谢谢。

var tt = readline().split(' ');
var a = parseInt(tt[0]);
var b = parseInt(tt[1]);

print(f([],a,b));
function f(arr,x,b){
    if (x>b){
        return [];
    }else if (x==b){
        return _add(arr,x);
    }else{
        return (f(_add(arr,x),(2*x),b) || f(_add(arr,x),(10*x+1),b));
    }
}

function _add(array,x){
    var _arr = array.slice();
    _arr.push(x);
    return _arr;
}

Answer 1

您需要返回false而不是空数组。空数组解析为 true 这意味着您仅迭代左分支。

(顺便说一句，如果零件返回，则不需要其他零件。)

function go(a, b) {
    //var tt = readline().split(' ');
    //var a = parseInt(tt[0]);
    //var b = parseInt(tt[1]);

    function f(arr, x, b) {
        if (x > b) {
            return false; // no []!!!
        } 
        if (x == b) {
            return _add(arr, x);
        }
        return (f(_add(arr, x), (2 * x), b) || f(_add(arr, x), (10 * x + 1), b));
    }

    function _add(array, x) {
        var _arr = array.slice();
        _arr.push(x);
        return _arr;
    }

    return f([], a, b);
}
console.log(go(2, 162));
console.log(go(4, 42));
console.log(go(100, 40021));

.as-console-wrapper { max-height: 100% !important; top: 0; }