Минимальная глубина двоичного дерева не работает для всех тестовых случаев - PullRequest
Новая
       55

Минимальная глубина двоичного дерева не работает для всех тестовых случаев

2 голосов
/ 10 апреля 2020

Я пытаюсь найти минимальную глубину двоичного дерева; однако мой тестовый пример в примере 5 не проходит. Я не уверен в недостатке в моей логике c, чтобы сделать эту работу для всех тестовых случаев. Пример того, что я делаю, выглядит следующим образом: 

Example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its minimum:
depth = 2

У меня есть следующий код для выполнения sh this: 

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = this.right = null;
  }
}

const minDepth = root => {
  if (!root) return 0

  const traverse = root => {
    let counter = 1
    if (!root) return counter
    let current
    let queue = [root, 's']

    while (queue.length > 1) {
      current = queue.shift()
      if (current === 's') counter++, queue.push('s')
      if (!current.left && !current.right) return counter
      else {
        if (current.left) queue.push(current.left)
        if (current.right) queue.push(current.right)
      }
    }
    return counter
  }
  return root.left && root.right ? Math.min(traverse(root.left), traverse(root.right)) + 1 : traverse(root)
}

//example 1  
const tree1 = new TreeNode(3)
tree1.left = new TreeNode(9)
tree1.right = new TreeNode(20)
tree1.right.left = new TreeNode(15)
tree1.right.right = new TreeNode(7)

//example 2
const tree2 = new TreeNode(1)
tree2.left = new TreeNode(2)
tree2.right = new TreeNode(3)
tree2.left.left = new TreeNode(4)
tree2.right.right = new TreeNode(5)

//example 3
const tree3 = new TreeNode(0)

//example 4
const tree4 = new TreeNode(1)
tree4.left = new TreeNode(2)

//example 5 not working
const tree5 = new TreeNode(1)
tree5.left = new TreeNode(2)
tree5.left.right = new TreeNode(3)
tree5.left.right.right = new TreeNode(4)
tree5.left.right.right.right = new TreeNode(5)


console.log(minDepth(tree1))
console.log(minDepth(tree2))
console.log(minDepth(tree3))
console.log(minDepth(tree4))
console.log(minDepth(tree5))

Есть мысли о том, что мне не хватает?

1 Ответ

3 голосов
/ 10 апреля 2020

Я немного не уверен в вашем общем подходе. Кажется, ваша функция настроена на выполнение рекурсии, но затем вы работаете итеративно внутри вложенной функции. Оба подхода имеют смысл для меня (рекурсия кажется более простой), но я бы рекомендовал четко фиксировать один или другой.

Если вы выберете итеративный, в основном вы запустите BFS и остановиться, когда вы нажмете первый листовой узел. Конечный узел - это узел без дочерних элементов, и нам необходимо обнаружить такой случай и для рекурсии.

Рекурсия просто передает 1 до родителя для каждого листа. В противном случае текущий узел является внутренним узлом; добавьте для него 1 и пропустите минимум рекурсии для его потомков (игнорируйте все, что не присутствует, объединив бесконечное значение для него). 

const minDepth = root => {
  if (!root) {
    return 0;
  }
  else if (!root.left && !root.right) {
    return 1;
  }
  
  return 1 + Math.min(minDepth(root.left) || Infinity,
                      minDepth(root.right) || Infinity);
};

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

/*
    3
   / \
  9   20
      / \
     15   7
     
     should be 2
*/
const tree1 = new TreeNode(3);
tree1.left = new TreeNode(9);
tree1.right = new TreeNode(20);
tree1.right.left = new TreeNode(15);
tree1.right.right = new TreeNode(7);

/*
     1
    / \
   2   3
  /     \
 4       5
 
  should be 3
*/
const tree2 = new TreeNode(1);
tree2.left = new TreeNode(2);
tree2.right = new TreeNode(3);
tree2.left.left = new TreeNode(4);
tree2.right.right = new TreeNode(5);

/*
  0
  
   should be 1
*/
const tree3 = new TreeNode(0);

/*
   1
  /
 2
 
  should be 2
*/
const tree4 = new TreeNode(1);
tree4.left = new TreeNode(2);

/*
       1
      /
     2
      \ 
       3
        \
         4
          \
           5
           
           should be 5
*/
const tree5 = new TreeNode(1);
tree5.left = new TreeNode(2);
tree5.left.right = new TreeNode(3);
tree5.left.right.right = new TreeNode(4);
tree5.left.right.right.right = new TreeNode(5);

console.log(minDepth(tree1));
console.log(minDepth(tree2));
console.log(minDepth(tree3));
console.log(minDepth(tree4));
console.log(minDepth(tree5));

Вот версия BFS: 

const minDepth = root => {
  for (const queue = [[root, 1]]; queue.length;) {
    const [node, depth] = queue.shift();
    
    if (node) {
      if (!node.left && !node.right) {
        return depth;
      }
      
      queue.push([node.left, depth + 1], [node.right, depth + 1]);
    }
  }

  return 0;
};

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

/*
    3
   / \
  9   20
      / \
     15   7
     
     should be 2
*/
const tree1 = new TreeNode(3);
tree1.left = new TreeNode(9);
tree1.right = new TreeNode(20);
tree1.right.left = new TreeNode(15);
tree1.right.right = new TreeNode(7);

/*
     1
    / \
   2   3
  /     \
 4       5
 
  should be 3
*/
const tree2 = new TreeNode(1);
tree2.left = new TreeNode(2);
tree2.right = new TreeNode(3);
tree2.left.left = new TreeNode(4);
tree2.right.right = new TreeNode(5);

/*
  0
  
   should be 1
*/
const tree3 = new TreeNode(0);

/*
   1
  /
 2
 
  should be 2
*/
const tree4 = new TreeNode(1);
tree4.left = new TreeNode(2);

/*
       1
      /
     2
      \ 
       3
        \
         4
          \
           5
           
           should be 5
*/
const tree5 = new TreeNode(1);
tree5.left = new TreeNode(2);
tree5.left.right = new TreeNode(3);
tree5.left.right.right = new TreeNode(4);
tree5.left.right.right.right = new TreeNode(5);

console.log(minDepth(tree1));
console.log(minDepth(tree2));
console.log(minDepth(tree3));
console.log(minDepth(tree4));
console.log(minDepth(tree5));
...