I opened a LeetCode membership and selected some high frequency topics. The purpose of this series is to help you spend 30 minutes a day on common interview questions, so that you can more skillfully interview. In this episode, we will explain the simple problem of three trees. Tree problems are always related to recursion, and recursion is the most difficult problem for beginners, because it is not easy to perform on paper, and when you write, you get confused. The data structures of the trees used in this issue are as follows:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(intx) { val = x; }}Copy the code

226. Flip the binary tree

Flip a binary tree, as shown below

This is a very typical entry recursion problem, a recursive function of a typical structure is the boundary condition + logical body, our core is naturally logical body. In this case, it is easy to think of using a temporary node, temp, to swap the logic of the left and right subtrees. It can be exchanged from top to bottom or from bottom to top. The complete code is as follows:

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

104. Maximum depth of a binary tree

Given a binary tree, return its maximum depth, as shown below

At first glance, the depth of each node is traversed first, the depth of each node is recorded, and then the maximum value is taken. So our first version of the code looks like this:

int maxnum=0;
public int maxDepth(TreeNode root) {
   help(root,0);
   return maxnum;
}
void help(TreeNode root,int num){
   if(root==null){
       maxnum=Math.max(num,maxnum);
       return;
   }
   num++;
   help(root.left,num);
   help(root.right,num);
}
Copy the code

Since in Java, when you change an int inside a function, the int outside the function does not change (for deeper reasons that are not explained here), num will only be +1 on the next recursion, and our code works. At the end of this question, there’s actually an amazing line of code that solves the problem:

int maxDepth(TreeNode root) {return root==null? 0 : Math.max(maxDepth2(root.left), maxDepth2(root.right))+1; }Copy the code

A line of code is a bit of a cheat. This line of code is very concise, but not as readable as the above, you can learn to learn.

Merge binary trees

Merge two binary trees, null=0, add val

The key is that both trees recurse to the left or right at the same time. The code is as follows:

public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
    if(t1==null&& t2! =null)
        return t2;
    if(t1==null && t2==null)
        return null;
    if(t1! =null && t2==null)
        return t1;
    if(t1! =null&& t2! =null){
        t1.val=t1.val+t2.val;
        t1.left=mergeTrees(t1.left,t2.left);
        t1.right=mergeTrees(t1.right,t2.right);
    }
    return t1;
}
Copy the code

So today we’re going to do a couple of problems with recursion, which is the simplest recursion. To help beginners understand recursion from a tree perspective, tomorrow we will cover three more simple tree problems, this time with a bias towards iteration, such as using data structures such as queues and stacks instead of recursive operations. Of course, if the basic students have fully mastered what we are talking about, then the day after tomorrow, we will start to introduce the middle questions in the high-frequency questions, will meet you.

Pay attention to wechat public number, more algorithm knowledge points to tell you.