Java 求解合并两个二叉树

本是古典何须时尚 2022-10-17 00:47 186阅读 0赞

### 文章目录 ###

*   *  一、题目
     *  二、递归分析
     *  三、总结

## 一、题目 ##

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70]

## 二、递归分析 ##

该题适用先序遍历，采用递归方法

（1）确定递归参数及返回值

> 由于需要遍历两颗二叉树，所以参数为两个结点

（2）确定递归终止条件

> 由于是需要合并结点，如果root1结点不存在，则返回root2结点，反之返回root1结点

（3）确定递归逻辑

> 先序遍历，先处理根节点，然后处理左子树和右子树

class Solution { 
        public TreeNode mergeTrees(TreeNode root1, TreeNode root2) { 
            //如果root1为空，则返回root2
            if (root1 == null) { 
                return root2;
            }
            //如果root2为空，则返回root1
            if (root2 == null) { 
                return root1;
            }
            //合并结点
            root1.val += root2.val;
            //递归处理左右子树
            root1.left = mergeTrees(root1.left, root2.left);
            root1.right = mergeTrees(root1.right, root2.right);
            return root1;
        }
    }

## 三、总结 ##

该题适用递归解决

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70]: /images/20221014/886b0be29d6b45719dabc2283a02e284.png