Find the largest search binary tree in the binary tree (tree BP)

Question Restatement:

Given the head node root of a binary tree, it is known that the values of all nodes are different. Find the search binary tree with the most nodes

Problem analysis:

We can judge each node and finally get the largest of all nodes

Solution:

Tree BP (recursive)

Problem solving:

code:

public class ReturnType{
    // The result we get needs the head node of the current node
    TreeNode root;
    // We need to judge the maximum by the subtree size of the current node
    int treeSize;
    // It is necessary to judge whether the left and right subtrees and the current node can meet the search binary tree, so the maximum and minimum values of the current tree are required
    int max;
    int min;
    public ReturnType() {}
		public ReturnType(TreeNode root,int treeSize,int max,int min){
			this.root = root;
			this.treeSize = treeSize;
			this.max = max;
			this.min = min;
		}
}
public TreeNode getMaxBST(TreeNode root){
    return process(root).root;
}
public ReturnType process(TreeNode root){
    // The current tree is null
    if(root == null){
        // Return a corresponding ReturnType node
        return new ReturnType(null,0,Integer.MIN_VALUE,Integer.MAX_VALUE);
    }
    // Gets the result of the current left subtree
    ReturnType lRoot = process(root.left);
    // Gets the result of the current right subtree
    ReturnType rRoot = process(root.right);
    // The current search binary tree is judged by the current node and the left and right subtrees of the current node
    // First, we need to judge the maximum node value and minimum node value in the subtree with the current node as the head node
    int max = Math.max(root.value,Math.max(lRoot.max,rRoot.max));
    int min = Math.min(root.value,Math.min(lRoot.min,rRoot.min));
    // Get the case of searching binary books with the left and right nodes as the maximum
    // Maximum number of nodes to search Binary Tree
    int treeSize = Math.max(lRoot.treeSize,rRoot.treeSize);
    // Maximum search for the head node of the binary tree
    TreeNode BSTRoot = (lRoot.treeSize > rRoot.TreeSize ? lRoot.root : rRoot.root);
    // When the current node is the head node, it is the largest search binary tree
    if(lRoot.treeSize == rRoot.treeSize && root.value > lRoot.max && root.value < rRoot.min){
        // In the third case, update the size of the head node and tree
        treeSize = lRoot.treeSize + rRoot.treeSize + 1;
        BSTRoot = root;
    }
    // Returns the record of the current node
    return new ReturnType(BSTRoot,treeSize,max,min);
}

Code analysis: tree dynamic programming decomposes a large problem into a small problem. We need to calculate the maximum search binary tree with a node as the head node. Then, we calculate the search binary tree of each node, and finally find the largest binary search tree from it. The implementation of this method should use recursive method

Recursive function: first, we judge the case that it is empty, and then let the left and right sub nodes of the current node call this function. At this time, we can understand that we have the results required by the current node and the left and right sub trees of the current node. Then we process the current node and the left and right subtrees to get the result we want.

Take the above topic as an example: we create a new type as the return value of the recursive function. The values in the new type are what we need to solve the problem. The topic requires to get the largest binary search tree and get the binary tree. We need the head node of the largest binary tree in the current binary tree, because we need to judge the size, We need the maximum number of search binary tree nodes in the current tree. To meet the binary search tree, we need to record the maximum and minimum values of the current binary tree. Therefore, our new type is:

	public static class ReturnType{
		public TreeNode root;
		public int treeSize;
		public int max;
		public int min;
		public ReturnType() {}
		public ReturnType(TreeNode root,int treeSize,int max,int min){
			this.root = root;
			this.treeSize = treeSize;
			this.max = max;
			this.min = min;
		}
	}

With the new type, we process the tree with the node as the head node in the recursive function. Because we already know the results in the current left and right subtrees, we can process each case and then return the results we need. There are three possibilities, one is the largest subtree in the left subtree, one is in the right subtree, and the other is the current tree. These three results can be processed separately

Summary:

Tree DP:

Premise of use: the final result we want to calculate can be decomposed into the calculation result with each node as the head node, and the final result is among them

Use steps:

1. Analyze all possible cases of taking a node as the head node to get the result
2. Create a new type according to all possible conditions, which is the data we need (if only a certain value is needed, no new type will be created)
3. The recursive function is designed. Firstly, judge the case that it is empty, and then call the recursive function on the left and right subtrees of the current subtree to get the results in the left and right subtrees of the current node
4. All possible cases are processed through the results of the current node and the left and right subtrees. The processing needs to get the data in the new type obtained with the current node as the head node, and then return the new type object