为什么我遍历树时超出了调用堆栈的最大尺寸？

我想从我的二叉树得到最小值，但我得到一个错误，最大调用堆栈大小已超出。如何正确获取二叉搜索树中项目的最小值？为什么我遍历树时超出了调用堆栈的最大尺寸？

这里是我的代码在：

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

function BinarySearchTree(){ 
    this.root = null; 
} 
BinarySearchTree.prototype.minNode =function() { 
    var node = this.root; 
    if(!node){ 
     return 0; 
    } 
    if(node.left){ 
     return this.minNode(node.left) 
    } 
    return node.value 
} 

BinarySearchTree.prototype.push = function(val){ 
    var root = this.root; 

    if(!root){ 
     this.root = new Node(val); 
     return; 
    } 

    var currentNode = root; 
    var newNode = new Node(val); 

    while(currentNode){ 
     if(val < currentNode.value){ 
      if(!currentNode.left){ 
       currentNode.left = newNode; 
       break; 
      } 
      else{ 
       currentNode = currentNode.left; 
      } 
     } 
     else{ 
      if(!currentNode.right){ 
       currentNode.right = newNode; 
       break; 
      } 
      else{ 
       currentNode = currentNode.right; 
      } 
     } 
    } 

} 

var bt = new BinarySearchTree(); 
bt.push(23); 
bt.push(1); 
bt.push(2); 
bt.push(25); 
console.log(bt.minNode());

来源

2017-06-29 user5711656

你不会推进'节点'。您在每次递归中将其设置为根。 – Li357

它不是最新的吗？什么是正确的方式.t获得最小值 – user5711656

您或者需要将它作为参数传递给递归方法，或者您需要在实例上保留一个'.currentSearchNode'属性并使用它来代替'this.root'你可以跟踪你在哪里。请注意，这对于任何有意义的数据集都可以很容易地溢出堆栈。 JavaScript在处理直接递归方面并不太好。相反，你总是可以蹦蹦跳跳。 –

像@AndrewLi提及。您再次设置相同的根，通过写

var node = this.root;

而是改变你的函数

BinarySearchTree.prototype.minNode =function(nextNode) { 
    var node = nextNode || this.root; 
    if(!node){ 
     return 0; 
    } 
    if(node.left){ 
     return this.minNode(node.left) 
    } 
    return node.value 
}

来源

2017-06-29 17:09:53 karthick

是的，我也在想同样的事情。但是，由于您在评论中首先回复了信用信息，所以您需要信用 – karthick

问题的定义是，你不前进的节点，当你穿越它。你只要继续设置node到根元素，因此它会永远递归。定义像这样的功能应该工作：

BinarySearchTree.prototype.minNode = function(nextNode) { 
    var node = nextNode || this.root; 
    if(!node) { 
    return 0; 
    } 
    if(node.left) { 
    return this.minNode(node.left) 
    } 
    return node.value 
}

这将使函数接受的下一个节点参数。然后它将分配node到下一个节点（如果它存在），或者如果它是第一个呼叫则分配给根。这不会一直递增，因为它会前进并穿过树。

来源

2017-06-29 17:10:53 Li357

为什么我遍历树时超出了调用堆栈的最大尺寸？

回答

相关问题