Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

Like it and see. Make it a habit. Wechat search [a coding] follow this programmer who is struggling in the Internet.

This article is collected on Github – Technical expert Training, which contains my learning route, series of articles, interview question bank, self-study materials, e-books, etc.

The recursion is done. Big dish chicken brush difficult in the problem.

— Leetcode

preface

Hello, everyone. I’m One.

Confused algorithm, rarely confused

The penultimate simple question!

Question

617. Merge binary trees

Difficulty: Easy

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:

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

Solution

As the comment says, recursion is necessary.

If you don’t have a clue, think of the two trees as two arrays

  • Terminating condition: The node in tree 1 or tree 2 is null

  • Recursive function: add the nodes of two trees, recursively execute the left node of two trees, recursively execute the right node of two trees

🤔 Think about how not to use the extra space?

Code

All LeetCode codes have been synchronized to Github

Welcome to star

/ * * *@author yitiaoIT
 */
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);
        merged.left = mergeTrees(t1.left, t2.left);
        merged.right = mergeTrees(t1.right, t2.right);
        returnmerged; }}Copy the code

Result

Complexity analysis

  • Time complexity: O(N)

Last

One foot is difficult to go, one hand is difficult to sing, a person’s power is limited after all, a person’s journey is doomed to be lonely. When you set a good plan, with full of blood ready to set out, must find a partner, and Tang’s monk to the West, the master and his disciples four people united as one to pass the ninety-eight difficult. So,

If you want to get into a big factory,

To learn data structures and algorithms,

If you want to keep brushing,

To have a group of like-minded people,

Please join the team to brush the questions