This is the 23rd day of my participation in Gwen Challenge

Merging binary trees (617)

Topic describes

Given two binary trees, imagine that when you overlay one of them on top of the other, some nodes of the two binary trees will overlap.

You need to merge them into a new binary tree. The rule for merging is that if two nodes overlap, their values are added as the new value of the nodes merged, otherwise a node that is not NULL is directly added as a node in the new binary tree.

Example 1:

Input: Tree 1 Tree 2 1 2 / \ / \ 3 2 1 3 / \ \ 5 4 7 Output: merged Tree: 3 / \ 4 5 / \ 5 4 7Copy the code

Note: The merge must start at the root of both trees.

Thought analysis

Merging two binary tree, that is to say, if the two at the same location of the node of the binary tree has a value, then the two nodes of the value added as a new binary tree node, when a node of a binary tree is null, if another node of the binary tree has a value, similarly also is additive, null as 0 for processing, If they’re all empty then this node in the new binary tree has no value.

This problem can be solved recursively by first creating a new node whose value is the sum of the two nodes of the old binary tree, and the left node of the new binary tree whose value is the sum of the positions of the two nodes of the old binary tree, as well as the right. So big problems can be reduced to small problems.

The code shown

Solution a:

    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        TreeNode newNode = null;
        if(root1 == null) {return root2;
        }
        if(root2 == null) {return root1;
        }
        newNode = new TreeNode(root1.val + root2.val);

        newNode.left = mergeTrees(root1.left,root2.left);
        newNode.right = mergeTrees(root1.right,root2.right);
        return newNode;

    }
Copy the code

Flipping binary tree

Topic describes

Flip the binary tree

Example:

Input:

4 / \ 27 / \ / \ 1 3 6 9Copy the code

Output:

4 / \ 7 2 / \ / 9 6 3 1Copy the code

Note: This question was inspired by Max Howell’s original question:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t flip a binary tree on a whiteboard during an interview. That’s too bad.

Thought analysis

Flip binary tree, this problem is actually quite simple, flip binary tree, which is to control node in the corresponding position of exchange, first of all, we exchanged our normal way of exchange value around the node, and then is the way of using a recursive process, recursive nodes left child node of left or right, big problem to resolve for small problems, termination conditions for this node is empty.

The code shown

Solution 1: Time complexity is O(n){O(n)}O(n), space complexity is O(1){O(1)}O(1).

 public TreeNode invertTree(TreeNode root) {
        if(root == null) {return null;
        }
        TreeNode temp = root.right;
        root.right = root.left;
        root.left = temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
Copy the code

conclusion

The combination of binary trees and the inversion of binary trees can be dealt with recursively. These two problems belong to the common use of recursion in binary trees. We should firmly grasp the use of recursion, so that we can have the opportunity to continue to break through in the later more complex problems.