You are given two binary trees root1 and root2.Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.Return the merged tree.Note: The merging process must start from the root nodes of both trees.
Question
You are given two binary trees root1 and root2.Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.Return the merged tree.Note: The merging process must start from the root nodes of both trees.
Solution
Here is a Python solution for the problem:
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def mergeTrees(root1, root2):
if not root1:
return root2
if not root2:
return root1
root1.val += root2.val
root1.left = mergeTrees(root1.left, root2.left)
root1.right = mergeTrees(root1.right, root2.right)
return root1
This solution works by recursively merging the two trees. It starts from the root nodes of both trees. If one of the nodes is null, it returns the other node. If both nodes are not null, it adds the values of the two nodes and updates the value of the first node. Then it recursively merges the left children and the right children of the two nodes. The merged tree is returned.
Similar Questions
Given the root of a binary tree, return the sum of all left leaves.A leaf is a node with no children. A left leaf is a leaf that is the left child of another node.
Given the roots of two binary trees p and q, write a function to check if they are the same or not.Two binary trees are considered the same if they are structurally identical, and the nodes have the same value. Example 1:Input: p = [1,2,3], q = [1,2,3]Output: trueExample 2:Input: p = [1,2], q = [1,null,2]Output: falseExample 3:Input: p = [1,2,1], q = [1,1,2]Output: false Constraints:The number of nodes in both trees is in the range [0, 100].-104 <= Node.val <= 104
Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.A leaf is a node with no children. Example 1:Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22Output: trueExplanation: The root-to-leaf path with the target sum is shown.Example 2:Input: root = [1,2,3], targetSum = 5Output: falseExplanation: There two root-to-leaf paths in the tree:(1 --> 2): The sum is 3.(1 --> 3): The sum is 4.There is no root-to-leaf path with sum = 5.Example 3:Input: root = [], targetSum = 0Output: falseExplanation: Since the tree is empty, there are no root-to-leaf paths. Constraints:The number of nodes in the tree is in the range [0, 5000].-1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
Given a Binary Tree of size N, your task is to complete the function rightLeafSum(), which should return the sum of all the leaf nodes that are the right child of their parent of the given binary tree.
If two trees have same structure and but different node content, then they are called ___a.Synonyms treesb.Joint treesc.Equivalent treesd.Similar trees
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.