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);
  }
}

- Jayson

---

你能否创建一个fiddle或snippet以便更好地理解？ - Help

让Tree等于新的tree(); Tree.addtotree(4); Tree.addtotree(3); Tree.addtotree(142); Tree.addtotree(15); Tree.addtotree(26); Tree.deepestnode(); // 返回 4 而不是 26 - Jayson

请提供addtotree()函数的实现。 - Dimitar

Answer 1

您需要花一些时间来学习递归 (https://zh.wikipedia.org/wiki/%E9%80%92%E5%BD%92)。有时候它会有点棘手。关于这个问题-这里有一个可行的例子：

    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);

- Dimitar

Answer 2

这是我的Javascript解决方案，仅用6行代码。它返回一个元组，其中包含树中最深的节点及其深度。我同意Dimitar的观点，你应该考虑使用递归编程。

需要记住的主要事项是递归函数的基本情况。在这个问题中，基本情况是树的叶子节点，即没有子节点的节点。从叶子节点无法进一步深入树中。

deepest(node = this.getRoot(), level = 0)  {
    // this is the base case, we return the node as it is a leaf
    if (!node.left && !node.right) return {'node' : node, 'level' : level}

    // we continue traversing the tree as we are not at a leaf node 
    // so there must be nodes at a deeper level
    let left = node.left ? this.deepest(node.left, level+1) : { 'level' : -1 }
    let right = node.right ? this.deepest(node.right, level+1) : { 'level' : -1 }

    // return the deeper node
    return (left.level > right.level) ? left : right
}

所以，根据您实现二叉树的方式，调用我的最深函数的一种方法可能是：

//you could pass in your root node into the function as a parameter
let obj = deepest() 

console.log('Deepest node: ' + obj.node.value + ', Level: ' + obj.level) 
// e.g 'Deepest node: 12, Level: 4'

- Iron Toad Tough