Javascript 最深节点

Question

我很难返回二叉树的最深节点。我知道如何找到树的高度，但我不知道如何返回最深的节点。下面是我的代码，因为我尝试循环整个树并替换参数中传递的节点。但是，结果我只得到了根节点。

tree.prototype.deepestnode=function()
{
  if(this.root===null)
  {
    return 'none';
  }
  else
  {
    let node=this.root;
    this.root.deepnode(1,1,node);
    return node;
  }
}

node.prototype.deepnode=function(maxdepth,currentdepth,node)
{
  if(maxdepth<currentdepth)
  {
    node=this;
  }
  if(this.left!==null)
  {
    this.left.deepnode(maxdepth,++currentdepth,this.left);
  } 
  if(this.right!==null)
  {   
    currentdepth++;    
    this.right.deepnode(maxdepth,++currentdepth,this.right);
  } 

}


 node.prototype.addnode=function(node)
{
  if(node.value<this.value)
  {
    if(this.left===null)
    {
      this.left=node;
    }
    else
      this.left.addnode(node);
  }
  else if(node.value>this.value)
  {
    if(this.right===null)
    {
      this.right=node;
    }
    else
      this.right.addnode(node);      
  }
}



tree.prototype.addtotree=function(value)
{
  let n=new node(value);
  if(this.root===null)
  {
    this.root=n;
  }
  else
  {
    this.root.addnode(n);
  }
}

Answer 1

你需要花一些时间在递归上( https://en.wikipedia.org/wiki/Recursion_(computer_science) 。有时这有点棘手。关于这个问题 - 这是一个工作示例:

    const tree = function () {
    this.root = {};

    this.add = function (root, node) {
        if (!root.value) {
            root.value = node.value;
            return;
        }

        if (root.value > node.value && !root.left) {
            root.left = node;
            return;
        }

        if (root.value <= node.value && !root.right) {
            root.right = node;
            return;
        }

        if (root.value > node.value) {
            this.add(root.left, node);
        } else {
            this.add(root.right, node);
        }
    }

    this.findDeepestNode = function (current, results, currentLevel) {
        if (results.length === 0) {
            results.push({ value: current.value, level: currentLevel })
        }

        if (!current.value) {
            return results;
        }

        if (current) {
            let currentDeepest = results.pop();
            if (currentDeepest.level > currentLevel) {
                results.push(currentDeepest);
            } else {
                results.push({ value: current.value, level: currentLevel });
            }
        }

        if (!current.left && current.right) {
            this.findDeepestNode(current.right, results, ++currentLevel);
        }


        if (!current.right && current.left) {
            this.findDeepestNode(current.left, results, ++currentLevel);
        }

        if (current.left && current.right) {
            this.findDeepestNode(current.left, results, ++currentLevel);
            this.findDeepestNode(current.right, results, currentLevel);
        }

        return results;
    }
};

const node = function (value) {
    this.value = value;
    this.left = {};
    this.right = {};
};

let t = new tree();
t.add(t.root, new node(4));
t.add(t.root, new node(3));
t.add(t.root, new node(2));
t.add(t.root, new node(142));
t.add(t.root, new node(15));
t.add(t.root, new node(26));
t.add(t.root, new node(13));
t.add(t.root, new node(28));

let deepest = t.findDeepestNode(t.root, [], 0);
console.log(deepest);