Javascript Deepest Node

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