当某些节点为空时，二叉树搜索不返回匹配值

Question

TL;DR - 如何将此算法更改为 return 给定具有空节点的 BST 的匹配值？

树节点：

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */

给定一个二叉树，找到匹配的值。我的算法如下

var searchBST = function(root, val) {
    const matchingNode = visitNode(root, val);
    // if no match, return null
    return matchingNode ? matchingNode : null;
};

const visitNode = (node, val) => {
    if (node.left !== null) {
        return visitNode(node.left, val)
    }
    if (node.right !== null) {
        return visitNode(node.right, val)
    }
    if (node.val === val) {
        console.log('MATCH!')
        return node;
    }
}

这适用于没有 null 值的标准树，例如 [4,2,7,1,3] 和空树 [].

我遇到了具有空节点的树的问题，例如 [18, 2, 22, null, null, null, 63, null, 84, null, null]。

该功能似乎过早停止。如果我删除前两个 if 块中的 returns，我可以在匹配的 val 处停止递归，但无法获得要 returned 的值。

如何将此算法更改为 return 给定具有空节点的 BST 的匹配值？

Answer 1

您可以考虑以下 visitNode() 的重构版本。基本情况发生在传入节点为 null 时，在这种情况下函数只是 returns null。否则，它检查当前节点是否匹配所寻找的值。如果不是，则递归向左或向右遍历。

const visitNode = (node, val) => {
    if (node == null) return null;

    if (node.val === val) {
        console.log('MATCH!')
        return node;
    }

    if (val < node.val) {
        return visitNode(node.left, val);
    }
    else {
        return visitNode(node.right, val)
    }
}

Answer 2

如果您正在寻找二叉搜索树，试试这个

if (node == null || node.val === val) 
   return node;
 
// val is greater than node's val
if (node->val < val) 
   return visitNode(node.right, val); 

// val is smaller than node's val
return visitNode(node.left, val);

或者你必须通过DFS or BFS

遍历树

当某些节点为空时，二叉树搜索不返回匹配值

Binary tree search not returning matching value when some nodes are null

javascript

algorithm

recursion

binary-search-tree