Невозможно изменить узел двоичного дерева в JavaScript - PullRequest
Новая
       13

Невозможно изменить узел двоичного дерева в JavaScript

0 голосов
/ 26 мая 2020

Это определение узла двоичного дерева в JavaScript. 

 function TreeNode(val, left, right) {
     this.val = (val===undefined ? 0 : val)
     this.left = (left===undefined ? null : left)
     this.right = (right===undefined ? null : right)
 }

Сейчас я пытаюсь инвертировать двоичное дерево. Это полный код. 

var invertTree = function(root) {
    if(root === null) return null
    else return invertTreeHelper(root, root.left, root.right)
};

var invertTreeHelper = function(node, left, right) {
    if(left === null && right === null) { return node } 
    else if(left === null && right !== null) {
            left = right
            right = null
            invertTreeHelper(node, left.left, left.right)
            return node
    } else if(left !== null && right === null) {
            console.log(right)
            right = left
            console.log(right)
            console.log(node)
            left = null
            invertTreeHelper(node, right.left, right.right)
            return node
    } else {
        console.log("swapping " + left.val + " and " + right.val)
        let temp = left.val
        left.val = right.val
        right.val = temp
        invertTreeHelper(node, left.left, right.right)
        invertTreeHelper(node, left.right, right.left)
        return node
    }
};

Однако именно с этой частью у меня возникли проблемы. Все остальное работает нормально. 

else if(left !== null && right === null) {
            console.log(right)
            right = left
            console.log(right)
            console.log(node)
            left = null
            invertTreeHelper(node, right.left, right.right)
            return node
    }

Итак, в показанной выше части я пытаюсь заменить нулевой узел ненулевым (существующий узел), но, похоже, это не меняет исходное дерево, потому что, когда я печатаю узел после того, как я его поменял местами, я вижу, что он заменен правильно, но исходное дерево не изменяется (оно остается нулевым в исходном дереве). Я пробовал node.left вместо того, чтобы просто вызывать left, и когда я это делаю, кажется, что исходное дерево изменяется, как я хочу, но я запутался, потому что в другой части кода, как показано ниже, я могу правильно поменять местами значения, просто вызвав left.val вместо node.left.val, и когда я распечатываю дерево, я вижу, что значения в исходном дереве были фактически изменены. Так что, возможно, все, что я спрашиваю, это почему замена значений с помощью left.val без вызова node.left.val, похоже, изменяет исходное дерево, но почему замена узлов только с left без вызова node.left - нет. Вот часть, где я меняю местами значения, и она изменяет исходное дерево. 

else {
        console.log("swapping " + left.val + " and " + right.val)
        let temp = left.val
        left.val = right.val
        right.val = temp
        invertTreeHelper(node, left.left, right.right)
        invertTreeHelper(node, left.right, right.left)
        return node
    }

Я новичок в деревьях, поэтому дайте мне знать, что мне не хватает. Спасибо.

1 Ответ

0 голосов
/ 26 мая 2020

Я считаю, что вам нужно присвоить возвращаемое значение - иначе ваша рекурсивная функция на самом деле работает неправильно. Может это? 

node = invertTreeHelper(node, left.left, right.right)
node = invertTreeHelper(node, left.right, right.left)
...