算法_每日一题(9.15)

简介: 算法_每日一题(9.15)

一、leetcode617. 合并二叉树

给你两棵二叉树: root1 和 root2 。

想象一下,当你将其中一棵覆盖到另一棵之上时,两棵树上的一些节点将会重叠(而另一些不会)。你需要将这两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新值;否则,不为

null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

示例 1:

29329556428a4713add091816b409421.png

输入:root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]

输出:[3,4,5,5,4,null,7] 示例 2:

输入:root1 = [1], root2 = [1,2] 输出:[2,2]


由题意所得,有两种思路,dfs和bfs,dfs主靠递归,bfs主靠队列

dfs:

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null){return root2;}
        if(root2 == null){return 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;
    }
}


bfs:

class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null) {
            return t2;
        }
        if (t2 == null) {
            return t1;
        }
        TreeNode merged = new TreeNode(t1.val + t2.val);
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        Queue<TreeNode> queue1 = new LinkedList<TreeNode>();
        Queue<TreeNode> queue2 = new LinkedList<TreeNode>();
        queue.offer(merged);
        queue1.offer(t1);
        queue2.offer(t2);
        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            TreeNode node = queue.poll(), node1 = queue1.poll(), node2 = queue2.poll();
            TreeNode left1 = node1.left, left2 = node2.left, right1 = node1.right, right2 = node2.right;
            if (left1 != null || left2 != null) {
                if (left1 != null && left2 != null) {
                    TreeNode left = new TreeNode(left1.val + left2.val);
                    node.left = left;
                    queue.offer(left);
                    queue1.offer(left1);
                    queue2.offer(left2);
                } else if (left1 != null) {
                    node.left = left1;
                } else if (left2 != null) {
                    node.left = left2;
                }
            }
            if (right1 != null || right2 != null) {
                if (right1 != null && right2 != null) {
                    TreeNode right = new TreeNode(right1.val + right2.val);
                    node.right = right;
                    queue.offer(right);
                    queue1.offer(right1);
                    queue2.offer(right2);
                } else if (right1 != null) {
                    node.right = right1;
                } else {
                    node.right = right2;
                }
            }
        }
        return merged;
    }
}


相关文章
|
10月前
|
算法
[算法刷题题解笔记] 洛谷 P1007 独木桥 [贪心]
[算法刷题题解笔记] 洛谷 P1007 独木桥 [贪心]
算法_每日一题(9.6)
算法_每日一题(9.6)
算法_每日一题(9.8)
算法_每日一题(9.8)
算法_每日一题(9.14)
算法_每日一题(9.14)
|
算法 测试技术 API
算法_每日一题(9.4)
算法_每日一题(9.4)
算法_每日一题(9.13)
算法_每日一题(9.13)
算法_每日一题(9.7)
算法_每日一题(9.7)
算法_每日一题(9.12)
算法_每日一题(9.12)
算法_每日一题(9.9)
算法_每日一题(9.9)