合并两个二叉树

Question

我想将一棵树与另一棵树合并，t。如果有重叠的数据，我想把它们加在一起。这是我现在的代码。我不明白如何仅使用参数 t 来执行此合并功能。 merge不是一般都有两个参数吗？

public class TreeFunctions {

   private TreeNode root;

   public TreeFunctions(TreeNode root) {
        this.root = root;
   }

   public TreeNode merge(TreeNode t) {
        TreeNode curr = this.root;
        if (curr == null) {
            return t;
        }

        if (t == null) {
            return curr;
        }

        curr.data += t.data;
        curr.left = merge(t.left);
        curr.right = merge(t.right);
        return curr;
   }
}

public class TreeNode{
    TreeNode left;
    TreeNode right;
    int data;

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

    public static String inOrder(TreeNode a) {
        if(a == null) return "";
        else return inOrder(a.left).trim() + " " + a.data + " " + inOrder(a.right).trim();
    }
}

编辑我的合并测试：

public void testMerge2() {
        TreeFunctions c = new TreeFunctions(new TreeNode(5, new TreeNode(2), null));
        TreeNode d = new TreeNode(2, new TreeNode(2), new TreeNode(1));
        TreeNode res2 = c.merge(d);
        assertEquals(TreeNode.inOrder(res2).trim(), "4 7 1");
    }

public void testMerge3() {
        TreeFunctions c = new TreeFunctions(new TreeNode(5, new TreeNode(2), null));
        TreeNode res2 = c.merge(null);
        assertEquals(TreeNode.inOrder(res2).trim(), "2 5");
    }

public void testMerge4() {
        TreeFunctions c = new TreeFunctions(new TreeNode(1, new TreeNode(2, new TreeNode(5), null), null));
        TreeNode res2 = c.merge(new TreeNode(1, null, new TreeNode(2, null, new TreeNode(5))));
        assertEquals(TreeNode.inOrder(res2).trim(), "5 2 2 2 5");
    }

Answer 1

我已经根据您的回复编辑了我的答案。我相信这就是您 want.Please 尝试并告诉我的。

在代码中，t1 和 t2 的函数都下降了一个级别，因此合并始终发生在同一级别和同一侧 (left-left/right-right)。

 public TreeNode merge(TreeNode t) {
        TreeNode curr = this.root; 
        merge2(curr,t);
        return curr;
   }
   public  void merge2(TreeNode t1,TreeNode t2) {
        if(t2==null)
            return;
        t1.data += t2.data;
        if(t2.left!=null)
        {
            if(t1.left==null)
                t1.left = new TreeNode(0);
            merge2(t1.left,t2.left);
        }
        if(t2.right!=null)
        {
            if(t1.right==null)
                t1.right = new TreeNode(0);
            merge2(t1.right,t2.right);
        }

   }

合并两个二叉树

Merging two binary trees

java

binary

tree

merge

binary-tree