当某些节点为空时，二叉树搜索不返回匹配值
当某些节点为空时，二叉树搜索不返回匹配值
提问于 2021-01-27 11:15:29
TL;DR -如何修改此算法以在给定具有空节点的BST的情况下返回匹配的val？
TreeNode：
/**
* 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}
*/给定一个二叉树，找到匹配的val。我的算法如下
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，63，null，84，null，null。
该功能似乎过早地停止了。如果我删除前两个If块中的返回，我可以在匹配的val处停止递归，但无法获得要返回的值。
如何修改此算法以返回给定具有空节点的BST的匹配val？
回答 2
Stack Overflow用户
回答已采纳
发布于 2021-01-27 11:23:58
您可以考虑下面重构后的visitNode()版本。基本情况发生在传入节点为null时，在这种情况下，函数只返回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)
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/65912440
复制相关文章
相似问题
腾讯云开发者
