算法日记-LeetCode-617.合并二叉树

2023-08-14

字数统计: 404字 | 阅读时长≈ 1分

算法日记-LeetCode-617.合并二叉树

原题链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目大意

给出两个二叉树，将两个二叉树重叠在一起

如果都有值，新节点值为两值和
如果只有一个有值，新节点与其相等
都为空，新节点为空

解题思路

根据题目的意思，我们需要将两个二叉树的重合的节点值相加，如果不是两个都有，那么就哪棵树有节点就用哪个，都没有则节点为空

两棵树 tree1, tree2

如果都有值 tree1.val + tree2.val
如果只有其中一个有 tree1.val 或者 tree2.val
都没有，节点为空

二叉树都可以通过递归方法来操作，操作对象分为：根节点、左子树、右子树

按照这个思路，给出一个merge函数，先merge根节点，再merge左右子树

merge根节点：判断tree1，tree2是否为空
merge左子树：merge tree1.left和tree2.left，走同样的merge逻辑
merge右子树：merge tree1.right 和 tree2.right

代码

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        TreeNode root = new TreeNode();
        if (root1 == null && root2 == null) return null;
        if (root1 != null && root2 != null) {
            root.val = root1.val + root2.val;
            root.left = mergeTrees(root1.left, root2.left);
            root.right = mergeTrees(root1.right, root2.right);
        }
        if (root1 == null) {
            root = root2;
        }
        if (root2 == null) {
            root = root1;
        }
        return root;
    }
}

简化

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) {
            root = root2;
        }
        if (root2 == null) {
            root = root1;
        }
        TreeNode root = new TreeNode(root1.val + root2.val);
        root.left = mergeTrees(root1.left, root2.left);
        root.right = mergeTrees(root1.right, root2.right);
        return root;
    }
}

本文作者： Naskete
本文链接： https://Naskete.github.io/2023/08/14/algorithm/算法日记-LeetCode-617.合并二叉树/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！