Слияние бинарных деревьев в Java - PullRequest
Новая
       8

Слияние бинарных деревьев в Java

1 голос
/ 01 апреля 2020

Я работаю над «Объединением двух двоичных деревьев» уже несколько часов и не могу понять, почему мой код не работает. Мне дано дерево t1 как [1,3,2,5] и дерево t2 как [2,1,3, null, 4, null, 7], и мне нужно объединить два дерева, суммируя перекрывающиеся узлы и избегая нулей, где возможно, поэтому результат должен быть [3,4,5,5,4, ноль, 7]. Вместо того, чтобы создавать новое дерево, как я должен, я переписываю дерево t1, чтобы получить желаемые результаты. Мой код выглядит следующим образом: 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        traversal(t1, t2);
        return t1;
    }

    public void traversal(TreeNode t1, TreeNode t2) {
        if(t2 == null) return;
        if(t1 == null)
            t1 = new TreeNode(0);
        t1.val += t2.val;
        traversal(t1.left, t2.left);
        traversal(t1.right, t2.right);
    }
}

Мой код выполняется без ошибок, и мой конечный результат - [3,4,5,5], что, очевидно, неверно. Кажется, что строка 

t1 = new TreeNode(0);

не делает то, что я хочу. Я хочу, чтобы текущий узел был изменен с нуля на значение 0, нулевой левый узел и нулевой правый узел, чтобы на следующей итерации программа повторяла только что созданный левый узел, который является нулевым.

Я попытался воссоздать все это (включая объявления классов / методов) в своей среде IDE, чтобы поиграть с ним и выполнить некоторую отладку, чтобы при необходимости я мог отредактировать свой полный код в этом посте, но я также могу Не могу понять, как сделать 

TreeNode(int val, TreeNode left, TreeNode right) {
  this.val = val;
  this.left = left;
  this.right = right;
}

, когда я хочу, чтобы либо левый, либо правый (но не оба) были нулевыми, поэтому мой полный код не такой чистый, как должен быть. В любом случае, может ли кто-нибудь помочь мне понять, почему мой код получает неправильный ответ для данного ввода?

1 Ответ

0 голосов
/ 01 апреля 2020

Полагаю, ваша проблема здесь в том, что приведенный ниже код на самом деле не выполняет то, что вы намеревались сделать. 

public void traversal(TreeNode t1, TreeNode t2) {
. . .
if(t1 == null)
    t1 = new TreeNode(0);
. . .

Здесь вы меняете локальную копию ссылки на точку на новый объект. Вы не меняете исходный объект . Фактически, вы не можете сделать это другим методом, чем исходный метод, в котором объект был изначально создан. Пожалуйста, смотрите java передача по значению .

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

...