java - 对两棵二叉树求和，并在第三棵二叉树中返回总和的结果

Question

所以我必须创建一个代码，可以对两个不同的二叉树求和，并在第三棵二叉树中返回它的结果。它必须使用递归来工作。这是我目前拥有的代码。它有点工作，但它不能递归工作。

   public BTree btNodeSum(BTree b, BTree b2) throws TreeException {
        if (isEmpty()) {
            throw new TreeException("Binary Tree is empty");
        }
        BTree tree = new BTree();
        tree.root = btNodeSum(b.root, b2.root);
        return tree;
    }
    
   private BTreeNode btNodeSum(BTreeNode b, BTreeNode b2) throws TreeException{
       BTreeNode n = new BTreeNode(0);
       if(b == null)
           return b2;
       if(b2 == null)
           return b;
       if(b.left != null && b2.left != null){
           b = btNodeSum(b.left, null);
           b2 = btNodeSum(null, b2.left);
           n.data = (int) btNodeSum(b, null).data  + (int) btNodeSum(null, b2).data;
       }
       else if(b.right != null && b2.right != null){
           b = btNodeSum(b.right, null);
           b2 = btNodeSum(null, b2.right);
           n.data =  (int) btNodeSum(b, null).data  + (int) btNodeSum(null, b2).data;
       }
       
       b = btNodeSum(b.left, null);
       b2 = btNodeSum(null, b2.left);
       b = btNodeSum(b.right, null);
       b2 = btNodeSum(null, b2.right);
       
       return n;
   }

我试图求和的两棵树具有以下值：

我得到的输出是这个：树 1 和树 2 的总和：PreOrder Tour: 8(null, 0),

我将不胜感激所有的帮助！

标签： javarecursiontree

Answer 1

两个二叉树之和的简单递归函数：

/**
 * Definition for a binary tree node.
 * public class BTreeNode {
 *     int val;
 *     BTreeNode left;
 *     BTreeNode right;
 *     BTreeNode() {}
 *     BTreeNode(int val) { this.val = val; }
 *     BTreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public BTreeNode btSum(BTreeNode t1, BTreeNode t2) {
        if(t1==null){
            return t2;
        }
        if(t2==null){
            return t1;
        }
        BTreeNode t3 = new BTreeNode();
        t3.val = t1.val + t2.val;
        t3.left = btSum(t1.left, t2.left);
        t3.right = btSum(t1.right, t2.right);
        return t3;
    }
}