On recursion -- binary tree recursion routine (pure personal understanding)

I found it difficult to recurse since I first came into contact with recursion in freshman year, and then I kept avoiding the big head of recursion. Recently, I picked up recursion and had a deeper understanding of recursion. This article is for reference only. If you are wrong, you can discuss it with me in the comment area (this method is from teacher Zuo Chengyun of niuke.com. I recommend you to sign up for his class, not advertising. You can decide according to your own economic strength).

First, let's start with the simplest recursion -- factorial

public static int fn(int x){
	if (x == 1) {
	     return 1;
	}
	return x*fn(x-1);
}

The whole process of recursion is as follows.

-->6*fn(5)

-->6*(5*fn(4)

-->6*(5*(4*fn(3)))

-->6*(5*(4*(3*fn(2))))

-->6*(5*(4*(3*(2*fn(1))))))

-->6*(5*(4*(3*(2*1))))

-->6*(5*(4*(3*2)))

-->6*(5*(4*6))

-->6*(5*24)

-->6*120

-->720

Recursion is the process that the system automatically presses the stack for us. We push the previous calculation that can not calculate the result into the stack. When we encounter the base case (return statement), a calculation result will pop up, and the last one will pop up one by one. This is the whole process of recursion. This section needs to draw a stack result and draw the process of pressing into the stack and bouncing the stack in turn, so as to have a deeper understanding.

Here, because it is relatively simple, everyone should be able to understand, but when it comes to more complex situations, we will find that recursion is as incomprehensible as metaphysics. Why can we suddenly get the result. Here I first introduce the recursive routine of binary tree.

(recursive traversal of binary tree can also help us understand recursion. We can try it manually)

First, the recursive routine of binary tree is to create a class as the return type, Each recursion returns a return type ", through this return type, we can easily get the result. I'll put out the code and you'll understand it. Let me first give an example. To judge whether a binary tree is a balanced binary tree, and to judge whether it is a balanced binary tree, we need to judge the height difference between the left and right children of each node, which is very consistent with our recursive idea. Therefore, when we recurse each node, we return two Key information: whether the left child of the node is a balanced binary tree (boolean isB) and the maximum height of the left child (int height), and whether the right child of the node is a balanced binary tree (boolean isB) and the maximum height of the right child (int height).

public class IsBanlenceTree {
	private static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}
	private static class ReturnType{
		private boolean isB;
		private int h;
		private ReturnType(Boolean isB,int h){
			this.isB = isB;
			this.h = h;
		}
	}
	private static boolean isB(Node head){
		return process(head).isB;
		
	}
	private static ReturnType process(Node head){
		//base case
		if(head == null){
			return new ReturnType(true, 0);
		}
		//Black box
		ReturnType leftReturnType = process(head.left);
		if (!leftReturnType.isB) {
			return new ReturnType(false, 0);
		}
		ReturnType rightReturnType = process(head.right);
		if (!rightReturnType.isB) {
			return new ReturnType(false, 0);
		}
		//Black box process
		if (Math.abs(leftReturnType.h - rightReturnType.h)>2 ) {
			return new ReturnType(false, 0);
		}
		int h = Math.max(leftReturnType.h, rightReturnType.h);
		return new ReturnType(true, h+1);
	}
}

This recursive method has three important parts: base case, recursion and recursive return value. We can understand this recursion as a black box. We will return the value regardless of why, and the part of "recursive return value" is the process of solving the black box. This is the "understanding routine" of binary tree recursion routine. But at the beginning of my contact, I wondered why recursion can get the value we want. In this way, recursion is really like metaphysics. But as we just said, recursion is actually the process that the system helps us automatically press the stack, so when we understand it ourselves, we can draw a stack result.

Suppose our binary tree looks like this

 

The recursive stack pressing process is as follows

 

When we continue to press here, the node we press in is empty, and the return value appears.

 

 

When a stack bounce occurs, it will continue to ReturnType rightReturnType = process(head.right), and the current head Right is also null, and a return type return new ReturnType(true, 0) will pop up; And then you can understand the process of receiving the black box.

if (Math.abs(leftReturnType.h - rightReturnType.h)>2 ) {
	return new ReturnType(false, 0);
}
   int h = Math.max(leftReturnType.h, rightReturnType.h);
   return new ReturnType(true, h+1);

The reason why the last return value here has a value is that our stack node ④ pops up two key information about its left and right children. At this time, both left and right children are balanced binary trees, and their maximum height is 0, plus themselves is 1. Therefore, node ④ also returns information to its parent node ②. If the parent node ② gets the information of its right child, it can get its own return type. This is the process of recursion.

A similar problem is to find the maximum distance of the binary tree and the maximum activity of the party.

The idea of solving the problem of the maximum distance of binary tree is that I need the information of the left tree and the information of the right tree. There are two cases,

① X does not participate: math Max (maximum distance from left tree, maximum distance from right tree)

② X participation: height of left tree + height of right tree

Therefore, our ReturnType needs to have the maximum distance and maximum height. The code is as follows (the following is the code of teacher Zuo Chengyun)

public class MaxDistanceInTree {
	public static class Node {
		public int value;
		public Node left;
		public Node right;
		public Node(int data) {
			this.value = data;
		}
	}
	public static class ReturnType{
		public int maxDistance;
		public int h;
		public ReturnType(int m,int h){
			this.maxDistance = m;
			this.h = h;
		}	
	}

	public static ReturnType maxDistance(Node head) {
		return process(head);
	}
	
	public static ReturnType process(Node head){
		if (head == null) {
			return new ReturnType(0, 0);
		}
		ReturnType leftReturnType = process(head.left);
		ReturnType rightReturnType = process(head.right);
		//Three cases
		int includeHeadDistance = leftReturnType.h +rightReturnType.h +1;
		int p1 = leftReturnType.maxDistance;
		int p2 = rightReturnType.maxDistance;
		//Black box
		int resultDistance = Math.max(Math.max(p1,p2),includeHeadDistance);//Find the three biggest cases
		int hitself = Math.max(leftReturnType.h,rightReturnType.h) + 1;//Here we need to calculate our own depth for recursion
		return new ReturnType(resultDistance, hitself);
	}

  

Every time I understand, I will think about what pops up when pressing the stack to the last pop-up stack, so as to think about what we should do to solve the black box. This is my idea to understand the binary tree recursive routine. Everyone has his own understanding, and you can find a way suitable for yourself. (finally, I would like to recommend Mr. Zuo Chengyun's class, because the teacher's code is pasted, and Mr. Zuo Chengyun really speaks very well. If you have the conditions, you can go to find out https://www.nowcoder.com/courses/cover/live/429)

 

Posted by simflex on Fri, 20 May 2022 22:06:01 +0300