The importance of binary trees

Take, for example, our classic algorithms “quicksort” and “merge sort”. What do you understand about these two algorithms? If you tell me that quicksort is a pre-traversal of a binary tree, and merge sort is a subsequent traversal of a binary tree, then I know you’re a good algorithm.

Why do quicksort and merge sort relate to binary trees? Let’s briefly analyze their algorithm ideas and code framework:

If nums[lo..p-1] is less than or equal to nums[p], and nums[p+1..hi] is greater than nums[p], and nums[p+1..hi] is greater than nums[p], and nums[p+1..hi] is greater than nums[p]. We recursively look for new cut-off points in numS [lo..p-1] and nums[p+1..hi], and finally the entire array is sorted.

The code framework for quicksort is as follows:

void sort(int[] nums, int lo, int hi) {
    /****** fore-traversal position ******/
    // Construct the boundary point p by swapping elements
    int p = partition(nums, lo, hi);
    / * * * * * * * * * * * * * * * * * * * * * * * * /

    sort(nums, lo, p - 1);
    sort(nums, p + 1, hi);
}
Copy the code

Construct the dividing point first, then construct the dividing point to the left and right subarray, you see this is not a binary tree before traversal?

[mid], [mid+1..hi], [mid+1..hi], [mid+1..hi], [mid+1..hi]

The code framework for merge sort is as follows:

void sort(int[] nums, int lo, int hi) {
    int mid = (lo + hi) / 2;
    sort(nums, lo, mid);
    sort(nums, mid + 1, hi);

    /****** after the sequence traversal location ******/
    // Merge two sorted subarrays
    merge(nums, lo, mid, hi);
    / * * * * * * * * * * * * * * * * * * * * * * * * /
}
Copy the code

Sort the left and right subarrays first, then merge (similar to merge ordered list logic), you see this is a binary tree after traversal framework? Plus, it’s the divide-and-conquer algorithm, but that’s all.

If you can see these sorting algorithms at a glance, do you need to memorize the algorithm code? It’s not easy to write an algorithm by slowly expanding from the framework.

All of this is just to show that the idea of binary trees is so widely used, that you can even abstract binary trees as long as it involves recursion.

The secret to writing a recursive algorithm

The key to writing a recursive algorithm is to know what the “definition” of a function is, then trust that definition, use that definition to derive the final result, and never try to jump into recursion.

To understand this, let’s use a concrete example. For example, let’s calculate how many nodes a binary tree has:

// Definition: count(root) returns the number of nodes in the root tree
int count(TreeNode root) {
    // base case
    if (root == null) return 0;
    // Add the number of nodes in the subtree to get the total number of nodes in the tree
    return 1 + count(root.left) + count(root.right);
}
Copy the code

Root is a node, plus the number of nodes in the left and right subtrees is the total number of nodes in the root tree.

What is the number of nodes in the left and right subtrees? Root. left and root.right, by definition, count the number of nodes in the root tree.

To write a tree dependent algorithm, simply put, you figure out what the root node is supposed to do and then recursively call the child node based on the function definition. The recursion calls the child node to do the same thing.

We’re going to do a couple of algorithm problems to actually do it.

Third, algorithm practice

Flip the binary tree

Through observation, we find that as long as the left and right child nodes of each node in the binary tree are swapped, the final result is a completely flipped binary tree.

The solution code can be written directly:

// Invert the whole tree \
TreeNode invertTree(TreeNode root) {
    // base case
    if (root == null) {
        return null;
    }

    /**** fore-traversal position ****/
    The root node needs to swap its left and right children
    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;

    // Let the left and right children continue to flip their children
    invertTree(root.left);
    invertTree(root.right);

    return root;
}
Copy the code

This problem is relatively simple, but the key idea is that we found that to flip the whole tree is to swap the left and right child nodes of each node, so we put the code to swap the left and right child nodes in the position of the preceding traversal.

It is worth mentioning that it is ok to swap the left and right child nodes in the post-traversal position, but not in the middle-traversal position. So the first thing I want to do is show you that one of the problems with binary trees is to break it down into what each node has to do.

This insight takes a lot of practice. Let’s move on to the next problem.

Populates the next right-side node pointer for each node

The function signature is as follows:

Node connect(Node root);
Copy the code

Join each level of the binary tree with a next pointer:

The input is a perfect binary tree. The entire binary tree is an equilateral triangle. Except for the right most node, the next pointer points to NULL, all nodes must have neighboring nodes to the right.

So how do we do this problem? To thread the nodes of each layer, is it just necessary to thread the left and right child nodes of each node?

We can copy the previous problem and write the following code:

Node connect(Node root) {
    if (root == null || root.left == null) {
        return root;
    }

    root.left.next = root.right;

    connect(root.left);
    connect(root.right);

    return root;
}
Copy the code

That’s a big problem. Look at this picture:

Node 5 and node 6 do not belong to the same parent node, so the logic of this code makes it impossible for both nodes to be threaded.

Recall that the difficulty of the binary tree problem is how to break down the requirements of the problem into what each node needs to do, but if you rely on only one node, there is no way to connect two neighboring nodes “across the parent node”.

If a node fails to do so, we can arrange two nodes for it. “Join each layer of binary tree nodes” can be further divided into “join every two adjacent nodes” :

// Main function \
Node connect(Node root) {
    if (root == null) return null;
    connectTwoNode(root.left, root.right);
    return root;
}

// Definition: Input two nodes to connect them
void connectTwoNode(Node node1, Node node2) {
    if (node1 == null || node2 == null) {
        return;
    }
    /**** fore-traversal position ****/
    // Join the two nodes passed in
    node1.next = node2;

    // Connect two children of the same parent
    connectTwoNode(node1.left, node1.right);
    connectTwoNode(node2.left, node2.right);
    // Connect two children across the parent node
    connectTwoNode(node1.right, node2.left);
}
Copy the code

In this way, connectTwoNode recurses continuously, covering the whole binary tree without dead angles, connecting all adjacent nodes, thus avoiding the previous problem and solving this problem.

The binary tree expands to a linked list

The function signature is as follows:

void flatten(TreeNode root);
Copy the code

Let’s try to define this function:

Enter a node root to the flatten function, and the root – rooted binary tree is flattened into a linked list.

Let’s see, how do we flatten a tree into a linked list? Very simple, the following process:

1. Flatten the left and right subtrees of root.

2. Connect the right subtree of root under the left subtree, and make the entire left subtree the right subtree.

How to flatten the left and right subtrees of root? Simply call the flatten function recursively on the left and right subtrees of root:

// Definition: Flatten a tree with root as a linked list
void flatten(TreeNode root) {
    // base case
    if (root == null) return;

    flatten(root.left);
    flatten(root.right);

    /**** after the sequence traversal location ****/
    // 1. The left and right subtrees have been flattened into a linked list
    TreeNode left = root.left;
    TreeNode right = root.right;

    // set left subtree as right subtree
    root.left = null;
    root.right = left;

    // add the original right subtree to the end of the current right subtree
    TreeNode p = root;
    while(p.right ! =null) {
        p = p.right;
    }
    p.right = right;
}
Copy the code

You see, that’s the beauty of recursion. How does the flatten function flatten the left and right subtrees? It’s not easy to say, but as long as you know the definition of Flatten, trust it, let root do what it does, and the Flatten function will work as defined.

Also note that the recursive framework is backward traversal, because we need to level the left and right subtrees before we can proceed.

The final summary

The key to recursive algorithms is to define the function, trust the definition, and not jump into the details of recursion.

Write binary tree algorithm questions, are based on the recursive framework, we should first understand the root node itself to do what, and then according to the requirements of the question to choose the use of pre-order, middle order, subsequent recursive framework.

The difficulty of binary tree problems lies in how to figure out what each node needs to do according to the requirements of the problems, which can only be practiced through multiple brush problems.