Summary of binary tree recursive routines

The time complexity of all previous binary tree recursion routines is $O(N)$, among $N$ Is the number of nodes in a binary tree , And they are all optimal solutions .

A node gets information from left and right children , Then integrate into this node , At this time, the left and right children are no longer needed , The parent node of this node also repeats this process , The whole process is equivalent to After the sequence traversal , Do dynamic planning on the tree , So it's called tree dp.

This routine includes two levels ：

1. Thought reminder
   How to achieve the goal ：X How to achieve the goal of a binary tree with root node ？
   Means of implementation ： Ask for information from the left and right trees , List the possibilities , This possibility must be based on the information from the left and right trees （ Constant time can be obtained ）, The processed information of the same magnitude is also constant time .
   Design information body , Analyze possibilities , The common classification is “ And target X of ” and “ And target X irrelevant ”.

2. Templates
   ① Design Info Information body ;
   ② process function ：process Function must return Info; When empty , If the value is bad, it will return null , Set it if it is good ;
   ③ By default, the left tree information is obtained first , Then get the right tree information ;
   ④ After analyzing the possibility , hold X All the necessary information is processed , This is highly templated .

This routine can solve most binary tree problems, especially tree type dp problem , The essence is to use Recursively traversing a binary tree The convenience of .

The whole process is summarized as follows ：

1） Suppose X Node as root , Suppose you can ask X Left tree and X The right tree wants any information

2） Under the assumptions of the previous step , Discuss with X Is the tree of the root node , Got the answer possibility （ above all ）

3） After listing all the possibilities , Determine what kind of information you need from the left tree and the right tree

4） Find the complete set of left tree information and right tree information , Is the information that any subtree needs to return S

5） Recursive functions return S, Every sub tree asks so

6） Write code , In the code, consider how to integrate the information of the left tree and the information of the right tree into the information of the whole tree