如何检查二叉树的右侧。在树中搜索项目

Question

我有一个数组。

const arr1 = [3, [ 8, [ 5, 4, null], 11], [ 7, [ 1, 0, null], null]]

我想写一个函数，它应该检查给定值是否在树中。

这是我的函数。

  function valueInTree(tree, val) {
    if(tree[0] === val || tree[1] === val || tree [2] === val){
        return true;
    }

    if (Array.isArray(tree[1])){
        return valueInTree(tree[1],val)
    }
    if (Array.isArray(tree[2])){
        return valueInTree(tree[2],val);
    }

    return false; 
}

console.log(valueInTree(arr1, 72));

下面是给定数组的视觉效果。

//                      3
//                    /   \
//                   8     7
//                  /\     /\
//                 5 11   1   N
//                /\     / \
//               4  72  0   N

所以，我的问题。如您所见，我的函数无法检查树的右侧。例如，它可以找到数字 3、8、5 和 4。但是当我尝试找到 7 或 11 时，它 returns false.

Answer 1

  function valueInTree(tree, val) {
    if(tree[0] === val || tree[1] === val || tree [2] === val){
        return true;
    }

    if (Array.isArray(tree[1])){
        if (valueInTree(tree[1],val))
          return true
    }
    if (Array.isArray(tree[2])){
        return valueInTree(tree[2],val);
    }

    return false; 
}

console.log(valueInTree(arr1, 72));

您的代码的唯一问题是它从不检查右子树，因为如果左子树是子树，它会直接 return 判断元素是否在其中。检查是否在左子树中找到该元素，并且 return 当且仅当它为真时才为真。通过这种方式，您也可以让算法有机会检查正确的子树。我做了一个小改动来实现这一点。

Answer 2

您可以直接测试 tree 然后检查值是否不是数组，然后 return false 否则检查左侧或右侧部分。

function valueInTree(tree, val) {
    if (tree === val) return true;
    if (!Array.isArray(tree)) return false;
    if (tree[0] === val) return true;
    return valueInTree(tree[1], val) || valueInTree(tree[2], val);
}

const tree = [3, [8, [5, 4, null], 11],  [7, [1, 0, null], null]]

console.log(valueInTree(tree, 72)); // false
console.log(valueInTree(tree, 1));  //  true
console.log(valueInTree(tree, 0));  //  true

如何检查二叉树的右侧。在树中搜索项目

How to check right side of Binary tree. Search item in a tree

javascript

arrays

algorithm

recursion

binary-tree