Arrange a given string in a Z-shape from top to bottom and from left to right according to the given number of lines. After that, your output needs to be read line by line from left to right to generate a new string.

Iterate over ss from left to right, adding each character to the appropriate line. The appropriate row can be tracked using the current row and current direction variables. The current direction will only change when we move up to the top row or down to the bottom row.

class Solution { public String convert(String s, int numRows) { if (numRows == 1) return s; List<StringBuilder> rows = new ArrayList<>(); //Storage the characters of each row after transformation for (int i = 0; i < Math.min(numRows, s.length()); i ) rows.add(new StringBuilder()); int curRow = 0; boolean goingDown = false; for (char c : s.toCharArray()) { //Traverse s directly, convert it into a character array, and assign it to c one by one rows.get(curRow).append(c); if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown; curRow = goingDown ? 1 : -1; } StringBuilder ret = new StringBuilder(); for (StringBuilder row : rows) ret.append(row); return ret.toString(); } }

Time O(n), where n=len(s), space O(n)

The import is at the top of the file, after the file comment. The import is usually a single line import or from ... import

1. Standard library import 2. Relevant third-party imports 3. Specific local application/library imports Put a blank line between each import group. Absolute imports are recommended because they are more readable; explicit relative imports can be used instead of absolute imports when dealing with complex package layouts, which are too verbose

1.int(x)

2.float(x)

3.str(x)

map(eval,list)

if type(n) == type(123):

stack.append()

stack.pop()

There is no peek method in the list. You can only pop first and then append.

queue.append()

queue.pop(0)

queue.append()

queue.popleft()

As everyone's development level improves and the complexity of the program increases, more and more modules and third-party libraries will be used in the program. The reason for this error is that the library "XX" is not installed, pip install ww

Download the corresponding third-party installation package and enter the download directory to install the full name of the downloaded file.

Install Microsoft Visual C 14.0, the blog has the download address visualcppbuildtools_full

pip3 install wheel

If it prompts which module file has an error, find this module, delete it, and replace it with the same file from a friend that can run.

1. The file name conflicts with python’s own keywords and the like.

2. Two py files import each other, causing one of them to be deleted.

pip version problem 10.0 does not have main(), Need to downgrade the version: python -m pip install –upgrade pip==9.0.1

Some APIs have changed after Pip v10, resulting in incompatibility between the old and new versions, which affects our installation and update of packages. Just update the IDE and you’re done! When updating, the IDE also gave us friendly prompts. PyCharm -> Help -> Check for Updates

Do not update the cracked version, otherwise the activation information will become invalid.

You named an asyncio py file If the check is not the first one, you need to check your python version because python3.7 and later only support the run method. 1 Upgrade python version 2 run is rewritten as follows loop = asyncio.get_event_loop() result = loop.run_until_complete(coro)

Replace constants files in asyncio

t=('a','b','c') for i in range(t):

Typical type error problem. In the above code, the range() function expects the incoming parameter to be an integer (integer), but the incoming parameter is a tuple (tuple). The solution is to change the input parameter tuple t to The number of tuples can be of integer type len(t). For example, change range(t) in the above code to range(len(t))

Caused by trying to modify the value of a string, which is an immutable data type

s[3] = 'a' becomes s = s[:3] 'a' s[4:]

Caused by trying to concatenate a non-string value with a string, just cast the non-string to a string with str()

When using the set function to construct a set, the elements in the given parameter list cannot contain lists as parameters.

When switching between python2 and python3, you will inevitably encounter some problems. In python3, Unicode strings are in the default format (str type), and ASCII-encoded strings (bytes type). The bytes type contains byte values ​​and is not actually a character. String, python3 and bytearray byte array type) must be preceded by operator b or B; in python2, it is the opposite, ASCII encoded string is the default, and Unicode string must be preceded by operator u or U

import chardet #Need to import this module and detect the encoding format encode_type = chardet.detect(html) html = html.decode(encode_type['encoding']) #Decode accordingly and assign it to the original identifier (variable)

>>> f=open ("hello.py") >>> f.write ("test")

The cause of the error is that the read-write mode parameter mode is not added to the incoming parameters of open("hello.py"), which means that the default way to open the file is read-only.

The solution is to change the mode mode to write mode permission w, f = open("hello. py", "w ")

Caused by forgetting to add colons at the end of statements such as if, elif, else, for, while, class and def

Incorrectly using "=" instead of "==". In Python programs, "=" is an assignment operator, and "==" is an equal comparison operation.

Most of the time this is because the file is not UTF8 encoded (for example, it may be GBK encoded) and the system uses UTF8 decoding by default. The solution is to change to the corresponding decoding method: with open('acl-metadata.txt','rb') as data:

open(path, ‘-mode-‘, encoding=’UTF-8’) i.e. open(path file name, read-write mode, encoding)

Commonly used reading and writing modes

When calling a function, there are not enough variables to accept the return value.

1. Restart pycharm (basically useless)

2. Set num_works to 0 (maybe useless)

3. Increase the size of the page file (completely solve the problem)

1. Not only is one project running, but the python program of another project is also running, just turn it off.

2. The windows operating system does not support python’s multi-process operation. The neural network uses multiple processes in data set loading, so set the parameter num_workers in DataLoader to 0.

0. Recently when I was running a scrapy project, the scrapy framework that was installed suddenly reported an error and I was caught off guard.

1. Because it is not difficult to install scrapy in Anaconda, it is not as simple and efficient as reinstalling to find a solution.

2. I can't completely uninstall it by just using the conda remove scrapy command. The reason may be that I installed scrapy twice using pip and conda respectively. Readers can try both pip and conda uninstall commands.

pip uninstall scrapy conda remove scrapy

Reinstall pip install scrapy

We only modified A.x, why was C.x also modified? In Python programs, class variables are treated internally as dictionaries, which follow the commonly cited method resolution order (MRO). So in the above code, since the x attribute in class C is not found, it will look up its base class (although Python supports multiple inheritance, there is only A in the above example). In other words, class C does not have its own x attribute, which is independent of A. Therefore, C.x is actually a reference to A.x

1. Local variable x has no initial value, and external variable X cannot be introduced internally.

Fool did not assign a value to lst, but fool2 did. You know, lst = [5] is the abbreviation of lst = lst [5], and we are trying to assign a value to lst (Python treats it as a local variable). In addition, our assignment to lst is based on lst itself (which is once again treated as a local variable by Python), but it has not been defined yet, so an error occurs! So here we need to distinguish between the use of local variables and external variables.

0.Get help

0. Change pip source

1. Install the specified library

2. Install the specified version of the specified library

3. Check which libraries are installed

4. View the specific information of the library

5.Where is pip installed?

6. Batch installation library

7. Install the library using the wheel file

8. Uninstall the library

9.Upgrade library

10. Save the library list to the specified file

11. Check the libraries that need to be upgraded

12. Check for compatibility issues

13. Download the library to local

pyinstaller -F filename.py

1. Parameters

2. Call

3.Method

subtopic

1. Expression of plus and minus infinity

1. In Python / means normal division with remainder, // means integer division with no remainder.

2. Non! in Python is represented by not

3.The square in Python is **

1. A colon must be added after all statements related to keywords: except return

2. There is no need to add () to the conditions in loops, judgments and other similar statements, and there are no {} in statement blocks. Use indentation to strictly represent the format.

1. Single line comment #

2. Multi-line comments ''' or """

dp = [[float('inf') for _ in range(n)] for _ in range(n)]

line, = ax.plot(x, np.sin(x))

Single line comments#

It is also the QQ lock shortcut key. Cancel the setting in QQ.

1.Navigation Bar navigation bar

1.appearance overall style

2.system settingssystem settings

1. According to the system view, you can search directly (comment note)

1.Font code font (adjustable size)

2.Color Scheme code area color scheme

3.Code Style code style

4.Inspections

5.File and Code Templates File and Code Templates

6.File Encodings file encoding

7.Live Templates dynamic templates (easy to use and master)

1.Project Interpret project interpreter

1.File

2.New Scratch File

3.Directory directory

4.Python File

5. When creating a new HTML file, you can right-click it and open it in a browser to see the display effect.

1. It is the same as the system CMD. You can install the package directly here and use the dos command.

You can directly write Python code, run it interactively, and edit it line by line.

It is equivalent to a memo. Write TODO ('') at the code point, so you can quickly find it and continue working. It can be used for mutual cooperation.

The strictness of code checking can be adjusted. The power saving mode is equivalent to placing the arrow to the far left. All grammatical errors will not be checked.

max_v, m_i = float(-inf), 0 #Combine a traversable data object (such as a list, tuple or string) into an index sequence, List both data subscripts and data for i, v in enumerate(nums): if v > max_v: max_v = v m_i = i

max_v = max(nums) m_i = nums.index(max_v)

1. As long as you see that the array given in the interview question is an ordered array, you can think about whether you can use the dichotomy method

2. The elements of the array are continuous in the memory address. An element in the array cannot be deleted individually, but can only be overwritten.

for (int i = 0; i < nums.length; i ) { for (int j = i 1; j < nums.length; j ) {

When there is a constraint that the head and tail cannot be at the same time, decompose the circular array into several ordinary array problems and find the maximum value

1. Left closed and right closed [left, right]

2. Close left and open right [left, right)

for (int i = 0; i < nums.length; i ) { int complement = target - nums[i]; if (map.containsKey(complement) && map.get(complement) != i)

1. When reversing the order: the possible carry issue of the last addition must be considered separately.

2. In forward sequence: reverse the linked list/use the data structure of the stack to achieve reversal

Assume that the left endpoint of the current linked list is left, the right endpoint is right, and the inclusion relationship is "left closed, right open". The given linked list is a one-way linked list. It is very easy to access subsequent elements, but it cannot directly access the predecessor elements. Therefore, after finding the median node mid of the linked list, if you set the relationship of "left closed, right open", you can directly use (left, mid) and (mid.next, right) to represent the list corresponding to the left and right subtrees No need for mid.pre, and the initial list can also be conveniently represented by (head, null)

Hash set: Set<Character> occ = new HashSet<Character>(); occ.contains(a)

int sum = carry x y; int carry = sum/10;

To "pop" and "push" numbers without the help of a auxiliary stack/array, we can use math, take out the last digit first, then divide by 10 to remove the last digit, invert the number and keep multiplying itself After 10, add the last digit taken out, and first determine whether it will overflow.

Take one step to the left, then keep walking to the right until you can't go any further

s = set(ls); lt = list(s)

lt = tuple(ls)

If a problem has many overlapping sub-problems, dynamic programming is most effective.

1. Determine the meaning of dp array (dp table) and subscripts 2. Determine the recursion formula 3.How to initialize the dp array 4. Determine the traversal order 5. Derivation of dp array with examples

Why determine the recursion formula first and then consider initialization? Because in some cases the recursive formula determines how to initialize the dp array

1. Print out the dp array and see if it is deduced according to your own ideas.

2. Before writing code, be sure to simulate the specific situation of the state transfer on the dp array, and be sure that the final result is the desired result.

When the recursive equation is only related to a few adjacent numbers, a rolling array can be used to optimize the space complexity to O(1)

Recursion termination condition, what this recursion does, and what it returns

The subscript of an array is an implicitly useful array, especially when counting some numbers (treating the corresponding array value as the subscript temp[arr[i]] of the new array), or determining whether some integers appear. time passed

1. When we give you a string of letters and ask you to determine the number of times these letters appear, we can use these letters as subscripts. When traversing, if the letter a is traversed, then arr[a] can be increased by 1. That is, arr[a]. Through this clever use of subscripts, we don’t need to judge letter by letter.

2. You are given n unordered int integer arrays arr, and the value range of these integers is between 0-20. You are required to sort these n numbers from small to large in O(n) time complexity. Print it out in large order, and use the corresponding value as the array subscript. If this number has appeared before, add 1 to the corresponding array.

When traversing the array, out-of-bounds judgment will be performed. If the subscript is almost out of bounds, we will set it to 0 and traverse again. Especially in some ring-shaped arrays, such as queues implemented with arrays pos = (pos 1) % N

For double pointers, it is particularly useful when doing questions about singly linked lists.

1. Determine whether a singly linked list has a cycle

2. How to find the middle node of the linked list in one traversal

3. The k-th node from the last in a singly linked list

subtopic

1. Sometimes when we perform division or multiplication operations, such as n / 2, n / 4, n / 8, we can use the shift method to perform the operation. Through the shift operation, The execution speed will be faster

2. There are also some operations such as & (and) and | (or), which can also speed up the operation.

1. To determine whether a number is odd, it will be much faster to use the AND operation.

1. In related issues of linked lists, we often set a head pointer, and this head pointer does not store any valid data. Just for the convenience of operation, we can call this head pointer the sentinel bit.

2. When operating an array, you can also set a sentinel, using arr[0] as the sentinel.

1. When we want to delete the first node, if a sentinel bit is not set, the operation will be different from the operation of deleting the second node. But we have set up a sentinel, so deleting the first node and deleting the second node are the same in operation, without making additional judgments. Of course, the same is true when inserting nodes

2. When you want to judge whether two adjacent elements are equal, setting a sentinel will not worry about cross-border problems. You can directly arr[i] == arr[i-1]. Don’t be afraid of crossing the boundary when i = 0

1. When we use recursion to solve a problem, it is easy to repeatedly calculate the same sub-problem. At this time, we must consider state preservation to prevent repeated calculations.

2.Examples

1. For recursive problems, we usually recurse from top to bottom until the recursion reaches the bottom, and then return the value layer by layer.

2. However, sometimes when n is relatively large, such as when n = 10000, then it is necessary to recurse down 10000 levels until n <= 2 before slowly returning the result. If n is too large, the stack space may be not enough

3. For this situation, we can actually consider a bottom-up approach.

4. This bottom-up approach is also called recursion

In Python, parameters can directly return part of the array nums[:i]. There is no need to redesign a method to intercept the array based on the subscript like in Java.

for i, v in enumerate(nums):

A stack in which the elements in the stack are monotonically increasing or decreasing. A monotonic stack can only be operated on the top of the stack.

1. The elements in the monotonic stack are monotonic.

2. Before elements are added to the stack, all elements that destroy the monotonicity of the stack will be deleted from the top of the stack.

3. Use the monotonic stack to find the element and traverse to the left to the first element that is smaller than it (incremental stack)/find the element and traverse to the left to the first element that is larger than it.

1. The keys of all nodes on the left subtree are less than the root node

2. The keywords of all nodes on the right subtree are greater than the root node

3. The left and right subtrees are each a binary sorting tree.

Inorder traversal can obtain increasing ordered sequence

1. Balanced binary tree: The absolute value of the height difference between the left and right subtrees of any node does not exceed 1

2. Balance factor: The height difference between the left and right subtrees of the node -1,0,1

Any tree that consists only of the edges of G and contains all the vertices of G is called a spanning tree of G.

Set of points: There is an edge connecting any two points.

Set of points: There is no edge between any two points

An undirected graph goes from a specified starting point to a specified end point, passing through all other nodes only once. A closed Hamiltonian path is called a Hamiltonian cycle, and a path containing all vertices in the graph is called a Hamiltonian path.

A hierarchical traversal algorithm similar to a binary tree, giving priority to the earliest discovered node.

Similar to pre-order traversal of a tree, the last discovered node is given priority.

1. The two data structures "queue" and "stack" can be implemented using either linked lists or arrays. If you implement it with an array, you have to deal with the problem of expansion and contraction; if you implement it with a linked list, you don't have this problem, but you need more memory space to store node pointers.

2. Two representation methods of "graph", adjacency list is a linked list, and adjacency matrix is ​​a two-dimensional array. The adjacency matrix determines connectivity quickly and can perform matrix operations to solve some problems, but it consumes space if the graph is sparse. Adjacency lists save space, but many operations are definitely not as efficient as adjacency matrices.

3. "Hash table" maps keys to a large array through a hash function. And as a method to solve hash conflicts, the zipper method requires linked list characteristics, which is simple to operate, but requires additional space to store pointers; the linear probing method requires array characteristics to facilitate continuous addressing and does not require storage space for pointers, but the operation is slightly complicated some

4. "Tree", implemented with an array is a "heap", because the "heap" is a complete binary tree. Using an array to store does not require node pointers, and the operation is relatively simple; using a linked list to implement it is a very common "tree", because It is not necessarily a complete binary tree, so it is not suitable for array storage. For this reason, various ingenious designs have been derived based on this linked list "tree" structure, such as binary search trees, AVL trees, red-black trees, interval trees, B-trees, etc., to deal with different problems.

1. Since arrays are compact and continuous storage, they can be accessed randomly, the corresponding elements can be found quickly through indexes, and storage space is relatively saved. But because of continuous storage, the memory space must be allocated at one time. Therefore, if the array wants to expand, it needs to reallocate a larger space and then copy all the data there. The time complexity is O(N); and if you want to When inserting and deleting in the middle of the array, all subsequent data must be moved each time to maintain continuity. The time complexity is O(N).

2. Because the elements of a linked list are not continuous, but rely on pointers to point to the location of the next element, there is no problem of array expansion; if you know the predecessor and successor of a certain element, you can delete the element or insert a new element by operating the pointer. Time complexity O(1). However, because the storage space is not continuous, you cannot calculate the address of the corresponding element based on an index, so random access is not possible; and because each element must store a pointer to the position of the previous and previous elements, it will consume relatively more storage space.

1.Array

2. Linked list

3. Binary tree

4.N-ary tree

void traverse(TreeNode root) { // Preorder traversal traverse(root.left) // In-order traversal traverse(root.right) // Postorder traversal }

The general form of dynamic programming problem is to find the optimal value. Dynamic programming is actually an optimization method in operations research, but it is more commonly used in computer problems. For example, it asks you to find the longest increasing subsequence and the minimum edit distance.

The core problem is exhaustion. Because we require the best value, we must exhaustively enumerate all possible answers and then find the best value among them.

1. Overlapping subproblems

2. Optimal substructure

3. State transition equation

1.Code

2. Recursive tree

3. Time complexity of recursive algorithm

1. Since the time-consuming reason is repeated calculations, we can create a "memo". Don't rush back after calculating the answer to a certain sub-question. Write it down in the "memo" before returning; every time you encounter a sub-question Check the problem in "Memo" first. If you find that the problem has been solved before, just take out the answer and use it instead of spending time calculating.

2. Generally, an array is used as this "memo". Of course, you can also use a hash table (dictionary)

3.Code

4. Recursive tree

5. Complexity

6.Comparison with dynamic programming

7. Top-down

8. Bottom-up

1. Thoughts

2.Code

3. State transition equation

4. State compression

You are given k coins with face values ​​of c1, c2...ck. The quantity of each coin is unlimited. Then you are given a total amount of money. I ask you how many coins you need at least to make up this amount. If it is impossible to make up the amount, , the algorithm returns -1

1. First of all, this problem is a dynamic programming problem because it has an "optimal substructure". To comply with the "optimal substructure", the subproblems must be independent of each other.

2. Back to the problem of collecting change, why is it said to be in line with the optimal substructure? For example, if you want to find the minimum number of coins when amount = 11 (original question), if you know the minimum number of coins when amount = 10 (sub-question), you only need to add one to the answer to the sub-question (choose another face value 1 coin) is the answer to the original question. Because the number of coins is unlimited, there is no mutual control between the sub-problems and they are independent of each other.

3. Four major steps

4. Pseudo code

5.Code

6. State transition equation

7. Recursive tree

8. Complexity

1.Code

2. Complexity

1.Definition of dp array

2.Code

3. Process

4.Details

Similar to the iteration of in-order traversal, with slight changes

class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); //Stack is implemented based on dynamic arrays, while LinkedList is implemented based on two-way linked lists. LinkedList is more efficient in adding, deleting, and modifying than Stack Deque<TreeNode> stk = new LinkedList<TreeNode>();//Double-ended queue //The node is not empty or the stack is not empty and the loop continues while (root != null || !stk.isEmpty()) { while (root != null) { res.add(root.val);//The root node is directly accessed and then pushed onto the stack stk.push(root); root = root.left;//After the root node ends, access its left child and become the new root node } root = stk.pop();//When jumping out of the loop, all left children have been accessed, and then the right child is accessed root = root.right; } return res; } }

class Solution: def preorderTraversal(self, root: TreeNode) -> List[int]: res = list() if not root: return res stack = [] node=root while stack or node:#The node is not empty or the stack is not empty and the loop continues while node: res.append(node.val) #The root node is directly accessed and then pushed onto the stack stack.append(node) node = node.left #After the root node ends, access its left child and become the new root node node = stack.pop() #When jumping out of the loop, all left children have been accessed, and then the right child is accessed node = node.right return res

Starting from the root node, each iteration pops the top element of the current stack and pushes its child node into the stack, first pressing the right child and then the left child.

class Solution { public List<Integer> preorderTraversal(TreeNode root) { LinkedList<TreeNode> stack = new LinkedList<>(); LinkedList<Integer> output = new LinkedList<>(); if (root == null) { return output; } stack.add(root); while (!stack.isEmpty()) { TreeNode node = stack.pollLast();//Retrieve and remove the last element of this list output.add(node.val); if (node.right != null) {//Only push one right and left child of the current node onto the stack, regardless of the others stack.add(node.right); } if (node.left != null) { stack.add(node.left); } } return output; } }

Time: O(n), Space: O(n)

1. Access the predecessor nodes of the pre-order traversal from the current node downwards, and each predecessor node is visited exactly twice.

2. First start from the current node, walk one step to the left child and then visit all the way down along the right child until reaching a leaf node (the in-order traversal predecessor node of the current node), so we update the output and create a pseudo edge predecessor. right = root updates the next point of this predecessor. If we visit the predecessor node for the second time, since it already points to the current node, we remove the pseudo edge and move to the next vertex.

3. If the movement to the left in the first step does not exist, directly update the output and move to the right

class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); TreeNode predecessor = null;//The predecessor node of the current node, the rightmost node of the left subtree while (root != null) { //According to whether there is a left child, determine whether to find its predecessor node or directly access the right child if (root.left != null) { //Find the predecessor first, then assign a value to its right child, and then traverse the left child of the current node //The predecessor node is the current root node, take one step to the left, and then keep walking to the right until it can no longer go. predecessor = root.left; while (predecessor.right != null && predecessor.right != root) { predecessor = predecessor.right; } //According to whether the right child of the predecessor is empty, determine whether to directly access the left subtree and then assign the value, or whether the left subtree access is completed. //Let predecessor's right pointer point to root and continue traversing the left subtree if (predecessor.right == null) { res.add(root.val); predecessor.right = root; root = root.left; } //Indicates that the left subtree has been visited. We need to disconnect the link and continue to visit the right subtree. else { predecessor.right = null; root = root.right; } } // If there is no left child, access the right child directly else { res.add(root.val); root = root.right; } } return res; } }

class Solution: def preorderTraversal(self, root: TreeNode) -> List[int]: res = list() if not root: return res p1=root while p1: p2 = p1.left #The predecessor node of the current node, the rightmost node of the left subtree if p2: #According to whether there is a left child, determine whether to find its predecessor node or directly access the right child while p2.right and p2.right != p1: p2 = p2.right #According to whether the right child of p2 is empty, determine whether to directly access the left subtree and then assign the value, or whether the left subtree access is completed. if not p2.right:#Let the right pointer of p2 point to p1 and continue traversing the left subtree res.append(p1.val) p2.right = p1 p1 = p1.left continue else: #Indicates that the left subtree has been visited, we need to disconnect the link and continue to visit the right subtree p2.right = None else: #If there is no left child, access the right child directly res.append(p1.val) p1 = p1.right return res

Time: O(n), Space: O(1)

This tree is traversed by visiting the left subtree - root node - right subtree, and when visiting the left subtree or right subtree, we traverse in the same way until the complete tree is traversed. Therefore, the entire traversal process is naturally recursive. We can directly use recursive functions to simulate this process.

class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); inorder(root, res); return res; } public void inorder(TreeNode root, List<Integer> res) { if (root == null) { return; } inorder(root.left, res); res.add(root.val); inorder(root.right, res); } }

class Solution: def preorderTraversal(self, root: TreeNode) -> List[int]: def dfs(cur): if not cur: return # Preorder recursion res.append(cur.val) dfs(cur.left) dfs(cur.right) # # In-order recursion #dfs(cur.left) # res.append(cur.val) #dfs(cur.right) # # Postorder recursion #dfs(cur.left) #dfs(cur.right) # res.append(cur.val) res = [] dfs(root) return res

Time complexity: O(n), where n is the number of binary tree nodes. In binary tree traversal, each node will be visited once and only once.

Space complexity: O(n). The space complexity depends on the stack depth of the recursion, and the stack depth will reach the O(n) level when the binary tree is a chain.

We can also implement the recursive function of method 1 in an iterative way. The two methods are equivalent. The difference is that a stack is implicitly maintained during recursion, and we need to explicitly simulate this stack during iteration.

class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); //Stack is implemented based on dynamic arrays, while LinkedList is implemented based on two-way linked lists. LinkedList is more efficient in adding, deleting, and modifying than Stack Deque<TreeNode> stk = new LinkedList<TreeNode>();//Double-ended queue //The node is not empty or the stack is not empty and the loop continues while (root != null || !stk.isEmpty()) { //Traverse the left child first until the left child is empty and end the loop while (root != null) { stk.push(root); root = root.left; } //When jumping out of the loop, the left child is empty. At this time, the one popped out of the stack is equivalent to the root node, and then it is the right child's turn. root = stk.pop(); res.add(root.val); root = root.right; } return res; } }

class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: res = list() if not root: return res stack = [] node=root while stack or node:#The node is not empty or the stack is not empty and the loop continues while node: stack.append(node) #Traverse the left child first until the left child is empty and end the loop node = node.left node = stack.pop() #The left child is empty when jumping out of the loop. At this time, the one popped out of the stack is equivalent to the root node, and then it is the right child's turn. res.append(node.val) node = node.right return res

Time: O(n), Space: O(n)

1. If x has no left child, first add the value of x to the answer array, and then access the right child of x, that is, x=x.right

2. If x has a left child, find the rightmost node on the left subtree of x (that is, the last node of the left subtree in the in-order traversal, and the predecessor node of x in the in-order traversal), which we record as predecessor. Depending on whether the right child of the predecessor is empty, perform the following operations

3. If the right child of the predecessor is empty, point its right child to x, and then access the left child of x, that is, x=x.left

4. If the right child of the predecessor is not empty, then its right child points to x at this time, indicating that we have traversed the left subtree of x. We leave the right child of the predecessor empty, add the value of x to the answer array, and then access The right child of x, that is, x=x.right

5. Repeat the above operations until the complete tree is visited

6. In fact, we will do one more step in the whole process: assuming that the currently traversed node is x, point the right child of the rightmost node in the left subtree of x to x, so that after the left subtree traversal is completed, we will use this pointer to Returns

class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); TreeNode predecessor = null;//The predecessor node of the current node, the rightmost node of the left subtree while (root != null) { //According to whether there is a left child, determine whether to find its predecessor node or directly access the right child if (root.left != null) { //Find the predecessor first, then assign a value to its right child, and then traverse the left child of the current node //The predecessor node is the current root node, take one step to the left, and then keep walking to the right until it can no longer go. predecessor = root.left; while (predecessor.right != null && predecessor.right != root) { predecessor = predecessor.right; } //Determine whether assignment or left subtree access ends based on whether the predecessor's right child is empty. //Let predecessor's right pointer point to root and continue traversing the left subtree if (predecessor.right == null) { predecessor.right = root; root = root.left; } //Indicates that the left subtree has been visited. At this time, visit the root node, then disconnect the link, and continue to visit the right subtree. else { res.add(root.val); predecessor.right = null; root = root.right; } } // If there is no left child, access the right child directly else { res.add(root.val); root = root.right; } } return res; } }

class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: res = list() if not root: return res p1=root while p1: p2 = p1.left #The predecessor node of the current node, the rightmost node of the left subtree if p2: #According to whether there is a left child, determine whether to find its predecessor node or directly access the right child while p2.right and p2.right != p1: p2 = p2.right #According to whether the right child of p2 is empty, determine whether to directly access the left subtree and then assign the value, or whether the left subtree access is completed. if not p2.right:#Let the right pointer of p2 point to p1 and continue traversing the left subtree p2.right = p1 p1 = p1.left continue else: #Indicates that the left subtree has been visited. At this time, visit the root node, then disconnect the link, and continue to visit the right subtree. res.append(p1.val) p2.right = None else: #If there is no left child, access the right child directly res.append(p1.val) p1 = p1.right return res

Time complexity: O(n), where n is the number of nodes in the binary search tree. Each node in Morris traversal will be visited twice, so the total time complexity is O(2n)=O(n)

Space complexity: O(1)

0. It has the efficiency of the stack iteration method and is as concise and easy to understand as the recursive method. More importantly, this method can write completely consistent code for pre-order, mid-order, and post-order traversal.

1. Use colors to mark the status of nodes. New nodes are white and visited nodes are gray. If the node encountered is white, mark it as gray, and then push its right child node, itself, and left child node onto the stack in sequence. If the node encountered is gray, the value of the node is output

2. If you want to implement pre-order and post-order traversal, you only need to adjust the stacking order of the left and right child nodes.

class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: WHITE, GRAY = 0, 1 #WHITE has not been visited, GRAY has visited res = [] stack = [(WHITE, root)] while stack: color, node = stack.pop() if node is None: continue if color == WHITE: #The order of mid-order is left, root, right, and the order of pushing into the stack is right, root, left. Adjust the order to complete other traversals. stack.append((WHITE, node.right)) stack.append((GRAY, node)) #The current node turns gray and has been visited stack.append((WHITE, node.left)) else: res.append(node.val) return res

Time: O(n), Space: O(n)

When returning to the root node, mark the current node to determine whether to return from the left subtree or the right subtree. When returning from the right subtree, start traversing the node

class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); Stack<TreeNode> stack = new Stack<>(); //The pre node is used to record the previously visited node, distinguishing between returning the root node from the left subtree or the right subtree. TreeNode pre = null; while(root!=null || !stack.empty()){ while(root!=null){ stack.push(root); //Continuously push the left node onto the stack root = root.left; } root = stack.peek();//Return from the left subtree, only get the root node and not pop it up, it has not been visited yet if(root.right==null || root.right==pre){ //If the right node is empty or the right node has been visited res.add(root.val); //You can access the root node at this time pre = root; stack.pop(); root = null; //At this time, do not push the left subtree onto the stack in the next cycle. It has already been pushed, and directly determine the top element of the stack. }else{ root = root.right; //Don't pop it off the stack yet, push its right node onto the stack } } return res; } }

class Solution: def postorderTraversal(self, root: TreeNode) -> List[int]: if not root: return list() res = list() stack = list() prev = None #The prev node is used to record the previously visited node, which distinguishes whether to return the root node from the left subtree or from the right subtree. while root or stack: while root: stack.append(root) #Continuously push the left node onto the stack root = root.left #This application uses peek, but there is no such method in the list. You can only pop first and then append. root = stack.pop() #Return from the left subtree, it has not been visited yet, and it will be added to the stack later. if not root.right or root.right == prev:#If the right node is empty or the right node has been visited res.append(root.val) #You can access the root node at this time prev = root #Record the current node root = None #At this time, do not push the left subtree onto the stack in the next cycle. It has already been pushed, and directly determines the top element of the stack. else: stack.append(root) #If it has not been accessed before, then add it to the stack root = root.right return res

//Modify the code for writing nodes into the result linked list in the preorder traversal code: change the insertion into the end of the queue to the insertion into the head of the queue //Modify the logic of checking the left node first and then the right node in the preorder traversal code: change to check the right node first and then the left node. //The pre-order traversal is the left and right roots, the reverse order is the right-left root, and the post-order traversal is the left and right roots. class Solution { public List<Integer> postorderTraversal(TreeNode root) { LinkedList res = new LinkedList(); Stack<TreeNode> stack = new Stack<>(); TreeNode pre = null; while(root!=null || !stack.empty()){ while(root!=null){ res.addFirst(root.val); //Insert the first of the queue stack.push(root); root = root.right; //First right then left } root = stack.pop(); root = root.left; } return res; } }

Time: O(n), Space: O(n)

1. The core idea of ​​Morris traversal is to use a large number of free pointers in the tree to achieve the ultimate reduction in space overhead. The subsequent rules for postorder traversal are summarized as follows:

2. If the left child node of the current node is empty, traverse the right child node of the current node.

3. If the left child node of the current node is not empty, find the predecessor node of the current node under in-order traversal in the left subtree of the current node.

4. If the right child node of the predecessor node is empty, set the right child node of the predecessor node to the current node, and update the current node to the left child node of the current node.

5. If the right child node of the predecessor node is the current node, reset its right child node to empty. Output all nodes on the path from the left child node of the current node to the predecessor node in reverse order. The current node is updated to the right child node of the current node

class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); if (root == null) { return res; } TreeNode p1 = root, p2 = null; //p1 current node, p2 predecessor node while (p1 != null) { p2 = p1.left; if (p2 != null) { while (p2.right != null && p2.right != p1) { p2 = p2.right; } if (p2.right == null) { p2.right = p1; p1 = p1.left; continue; } else { p2.right = null; addPath(res, p1.left); } } p1 = p1.right; } addPath(res, root); return res; } public void addPath(List<Integer> res, TreeNode node) { int count = 0; while (node ​​!= null) { count; res.add(node.val); node = node.right; } //Reverse the newly added nodes int left = res.size() - count, right = res.size() - 1; while (left < right) { int temp = res.get(left); res.set(left, res.get(right)); res.set(right, temp); left ; right--; } } }

class Solution: def postorderTraversal(self, root: TreeNode) -> List[int]: def addPath(node: TreeNode): count = 0 while node: count = 1 res.append(node.val) node = node.right #Reverse the newly added nodes i, j = len(res) - count, len(res) - 1 while i < j: res[i], res[j] = res[j], res[i] #No intermediate variables required i = 1 j -= 1 if not root: return list() res = list() p1=root while p1: p2 = p1.left #p2 predecessor node if p2: while p2.right and p2.right != p1: p2 = p2.right if not p2.right: p2.right = p1 p1 = p1.left continue else: p2.right = None addPath(p1.left) p1 = p1.right addPath(root) return res

Time: O(n), Space: O(1)

1. If we know the maximum depth l and r of the left subtree and the right subtree, then the maximum depth of the binary tree is max(l,r) 1

2. The maximum depth of the left subtree and right subtree can be calculated in the same way. Therefore, when we calculate the maximum depth of the current binary tree, we can first recursively calculate the maximum depth of its left subtree and right subtree, and then calculate the maximum depth of the current binary tree in O(1) time. Recursion exits when an empty node is reached

class Solution { public int maxDepth(TreeNode root) { if(root==null) return 0;//When the last 1 is a leaf node, the height will be returned to 1 return Math.max(maxDepth(root.left),maxDepth(root.right)) 1; } }

class Solution: def maxDepth(self, root: TreeNode) -> int: if not root: return 0 lefth = self.maxDepth(root.left) #You must use self.self when calling yourself righth = self.maxDepth(root.right) return max(lefth,righth) 1

Time complexity: O(n), where n is the number of binary tree nodes. Each node is traversed only once in the recursion

Space complexity: O(height), where height represents the height of the binary tree. Recursive functions require stack space, and the stack space depends on the depth of the recursion, so the space complexity is equivalent to the height of the binary tree

The queue of breadth-first search stores "all nodes of the current layer". Every time we expand the next layer, unlike breadth-first search which only takes out one node from the queue at a time, we need to take out all the nodes in the queue for expansion, so as to ensure that the queue is expanded every time Stored in are all the nodes of the current layer, that is, we expand layer by layer. Finally, we use a variable ans to maintain the number of expansions. The maximum depth of the binary tree is ans

class Solution { public int maxDepth(TreeNode root) { if (root == null) { return 0; } Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root); int ans = 0; while (!queue.isEmpty()) { int size = queue.size(); while (size > 0) { //operate one layer of elements at a time TreeNode node = queue.poll(); if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } size--; } ans ;//After one layer of operation is completed, the number of layers is 1 } return ans; } }

import collections class Solution: def maxDepth(self, root: TreeNode) -> int: if not root: return 0 queue = collections.deque() queue.append(root) ans = 0 while queue: ans = 1 for _ in range(len(queue)): #Traverse the elements of one level each time node = queue.popleft() if node.left: queue.append(node.left) if node.right: queue.append(node.right) return ans

Time complexity: O(n), where n is the number of nodes in the binary tree. The same analysis as method 1, each node will only be visited once

Space complexity: The space consumption of this method depends on the number of elements stored in the queue, which will reach O(n) in the worst case

We start from the root node, recursively traverse the tree, and start flipping from the leaf nodes first. If the left and right subtrees of the currently traversed node root have been flipped, then we only need to exchange the positions of the two subtrees to complete the flipping of the entire subtree with root as the root node.

class Solution { public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } //Traverse the tree recursively and start flipping from the leaf nodes first TreeNode left = invertTree(root.left); TreeNode right = invertTree(root.right); root.left = right; root.right = left; return root; } }

class Solution: def invertTree(self, root: TreeNode) -> TreeNode: if not root: return root #Traverse the tree recursively and start flipping from the leaf nodes first left = self.invertTree(root.left) right = self.invertTree(root.right) root.left, root.right = right, left return root

Time complexity: O(N), where N is the number of binary tree nodes. We will traverse each node in the binary tree, and for each node, we exchange its two subtrees in constant time

Space complexity: O(N). The space used is determined by the depth of the recursion stack, which is equal to the height of the current node in the binary tree. Under average circumstances, the height of a binary tree has a logarithmic relationship with the number of nodes, which is O(logN). In the worst case, the tree forms a chain, and the space complexity is O(N)

Given an integer n, how many binary search trees are there with 1...n as nodes?

1. Traverse each number i, use the number as the root of the tree, use the 1⋯(i−1) sequence as the left subtree, and use the (i 1)⋯n sequence as the right subtree. Then we can recursively construct the left subtree and right subtree in the same way

2. Since the root values ​​are different, we can ensure that each binary search tree is unique

3. The original problem can be decomposed into two smaller sub-problems, and the solutions to the sub-problems can be reused. Dynamic programming can be used to solve this problem

4. We can define two functions: G(n): The number of different binary search trees that can be formed by a sequence of length n. F(i,n): The number of different binary search trees with i as the root and sequence length n (1≤i≤n). It can be seen that G(n) is the function we need to solve

5. The total number of different binary search trees G(n) is the sum of F(i,n) that traverses all i(1≤i≤n)

6. For boundary cases, when the sequence length is 1 (only the root) or 0 (empty tree), there is only one situation, namely: G(0)=1, G(1)=1

7. Select the number i as the root, then the set of all binary search trees with the root i is the Cartesian product of the left subtree set and the right subtree set

8. Combine the two formulas:

class Solution { public int numTrees(int n) { int[] G = new int[n 1]; G[0] = 1; G[1] = 1; for (int i = 2; i <= n; i) { for (int j = 1; j <= i; j) { G[i] = G[j - 1] * G[i - j]; } } return G[n]; } }

class Solution: def numTrees(self, n): G = [0]*(n 1) #List of length n 1 G[0], G[1] = 1, 1 for i in range(2, n 1): #Traverse from G[2] to n for j in range(1, i 1): #Corresponding summation formula from 1 to n G[i] = G[j-1] * G[i-j] return G[n]

Time complexity: O(n^2), where n represents the number of nodes in the binary search tree. The G(n) function has a total of n values ​​that need to be solved. Each solution requires O(n) time complexity, so the total time complexity is O(n^2)

Space complexity: O(n). We need O(n) space to store G array

1. The value of the G(n) function derived in method 1 is mathematically called the Catalan number Cn ​

class Solution { public int numTrees(int n) { // Tip: We need to use the long type here to prevent overflow during calculation. long C = 1; for (int i = 0; i < n; i) { C = C * 2 * (2 * i 1) / (i 2); } return (int) C; } }

class Solution(object): def numTrees(self, n): C=1 for i in range(0, n): C = C * 2*(2*i 1)/(i 2) return int(C)

Time complexity: O(n), where n represents the number of nodes in the binary search tree. We only need to loop through it once

Space complexity: O(1). We only need constant space to store several variables

Given an integer n, generate all binary search trees consisting of nodes 1...n

1. Assume that the current sequence length is n, and if we enumerate the value of the root node as i, then according to the properties of the binary search tree, we can know that the set of node values ​​​​of the left subtree is [1...i−1], and the set of node values ​​​​of the right subtree is [1...i−1]. The set of node values ​​of the tree is [i 1…n]. Compared with the original problem, the generation of left subtree and right subtree is a sub-problem with reduced sequence length, so we can think of using recursive methods to solve this problem.

2. Define the generateTrees(start, end) function to indicate that the current value set is [start, end] and return all feasible binary search trees generated by the sequence [start, end]. According to the above idea, we consider that the value ii in the enumeration [start, end] is the root of the current binary search tree, then the sequence is divided into two parts: [start, i−1] and [i 1, end]. We call these two parts recursively, namely generateTrees(start, i - 1) and generateTrees(i 1, end), to obtain all feasible left subtrees and feasible right subtrees. Then in the last step, we only need to collect the feasible left subtrees from the feasible left subtrees Select one, then select one from the feasible right subtree set and splice it to the root node, and put the generated binary search tree into the answer array.

3. The entry point of recursion is generateTrees(1, n), and the exit point is when \textit{start}>\textit{end}start>end, the current binary search tree is empty, just return an empty node.

class Solution: def generateTrees(self, n: int) -> List[TreeNode]: def generateTrees(start, end): if start > end: return [None,] allTrees = [] for i in range(start, end 1): # Enumerate feasible root nodes #First complete the recursive construction of the left and right subtrees, and then use the completed set of left and right subtrees to build a complete tree leftTrees = generateTrees(start, i - 1) # Get the set of all feasible left subtrees rightTrees = generateTrees(i 1, end) # Get the set of all feasible right subtrees # Select a left subtree from the left subtree set, select a right subtree from the right subtree set, and splice them to the root node for l in leftTrees: #Relationship of Descartes product for r in rightTrees: currTree = TreeNode(i) #Root node currTree.left = l currTree.right = r allTrees.append(currTree) return allTrees return generateTrees(1, n) if n else []

Time complexity: The time complexity of the entire algorithm depends on the "number of feasible binary search trees", and the number of binary search trees generated for n points is equivalent to the nth "Cattleya number" in mathematics, using G_n means. Readers are asked to check the specific details of Cattleya number by themselves. I will not go into details here and only give the conclusion. Generating a binary search tree requires O(n) time complexity. There are G_n binary search trees in total, which is O(nG_n)

Space complexity: There are Gn binary search trees generated by n points, each tree has n nodes, so the storage space requires O(nG_n)

Given two binary trees, imagine that when you overlay one of them onto the other, some of the nodes of the two binary trees overlap. You need to merge them into a new binary tree. The rule of merging is that if two nodes overlap, then their values ​​are added as the new value after the node is merged. Otherwise, the node that is not NULL will be directly used as the node of the new binary tree.

1. Traverse two binary trees simultaneously starting from the root node, and merge the corresponding nodes. The corresponding nodes of the two binary trees may have the following three situations, and use different merging methods for each situation.

2. If the corresponding nodes of the two binary trees are empty, the corresponding nodes of the merged binary tree will also be empty.

3. If only one of the corresponding nodes of the two binary trees is empty, the corresponding node of the merged binary tree will be the non-empty node.

4. If the corresponding nodes of the two binary trees are not empty, the value of the corresponding node of the merged binary tree is the sum of the values ​​of the corresponding nodes of the two binary trees. At this time, the two nodes need to be merged explicitly.

5. After merging a node, the left and right subtrees of the node must be merged respectively. This is a recursive process

class Solution { public TreeNode mergeTrees(TreeNode t1, TreeNode t2) { if (t1 == null) { return t2; } if (t2 == null) { return t1; } //First merge the current node, and then recurse its left and right subtrees TreeNode merged = new TreeNode(t1.val t2.val); merged.left = mergeTrees(t1.left, t2.left); merged.right = mergeTrees(t1.right, t2.right); return merged; } }

class Solution: def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode: if not t1: return t2 if not t2: return t1 #First merge the current node, and then recurse its left and right subtrees merged = TreeNode(t1.val t2.val) merged.left = self.mergeTrees(t1.left, t2.left) merged.right = self.mergeTrees(t1.right, t2.right) return merged

Time complexity: O(min(m,n)), where m and n are the number of nodes of the two binary trees respectively. Depth-first search is performed on two binary trees at the same time. Only when the corresponding nodes in the two binary trees are not empty, the node will be explicitly merged. Therefore, the number of nodes visited will not exceed the number of the smaller binary tree. Number of nodes

Space complexity: O(min(m,n)), where m and n are the number of nodes of the two binary trees respectively. The space complexity depends on the number of levels of recursive calls. The number of levels of recursive calls will not exceed the maximum height of the smaller binary tree. In the worst case, the height of the binary tree is equal to the number of nodes.

Implement a binary search tree iterator. You will initialize the iterator using the root node of the binary search tree. Calling next() will return the next smallest number in the binary search tree

1. The simplest way to implement an iterator is on an array-like container interface. If we have an array, we only need a pointer or index to easily implement the functions next() and hasNext()

2. Use an additional array and expand the binary search tree to store it. We want the elements of the array to be sorted in ascending order, then we should perform an in-order traversal of the binary search tree, and then we build an iterator function in the array

3. Once all nodes are in the array, we only need a pointer or index to implement the next() and hasNext functions. Whenever hasNext() is called, we just need to check if the index reaches the end of the array. Whenever next() is called, we simply return the element pointed to by the index and move forward one step to simulate the progress of the iterator

class BSTIterator { ArrayList<Integer> nodesSorted; int index; public BSTIterator(TreeNode root) { this.nodesSorted = new ArrayList<Integer>(); this.index = -1; this._inorder(root); } private void _inorder(TreeNode root) { if (root == null) return; this._inorder(root.left); this.nodesSorted.add(root.val); this._inorder(root.right); } public int next() { return this.nodesSorted.get( this.index); } public boolean hasNext() { return this.index 1 < this.nodesSorted.size(); } }

class BSTIterator: self.nodes_sorted = [] self.index = -1 self._inorder(root) def __init__(self, root: TreeNode): self.nodes_sorted = [] self.index = -1 self._inorder(root) def _inorder(self, root): if not root: return self._inorder(root.left) self.nodes_sorted.append(root.val) self._inorder(root.right) def next(self) -> int: self.index = 1 return self.nodes_sorted[self.index] def hasNext(self) -> bool: return self.index 1 < len(self.nodes_sorted)

Time complexity: The time spent constructing the iterator is O(N). The problem statement only requires us to analyze the complexity of the two functions, but when implementing the class, we must also pay attention to the time required to initialize the class object; in this case Below, the time complexity is linearly related to the number of nodes in the binary search tree: next(): O(1), hasNext(): O(1)

Space complexity: O(N), since we created an array to contain all node values ​​in the binary search tree, which does not meet the requirements in the problem statement, the maximum space complexity of any function should be O(h) , where h refers to the height of the tree. For a balanced binary search tree, the height is usually logN

1. The method used previously has a linear relationship in space with the number of nodes in the binary search tree. However, the reason we have to use this approach is that we can iterate over the array, and we cannot pause the recursion and then start it at some point. However, if we can simulate controlled recursion with inorder traversal, we don't actually need to use any other space than the space on the stack used to simulate the recursion

2. Use an iterative method to simulate in-order traversal instead of a recursive method; in the process of doing this, we can easily implement the calls of these two functions instead of using other extra space

3. Initialize an empty stack S, used to simulate in-order traversal of a binary search tree. For in-order traversal we use the same method as before, except that we now use our own stack instead of the system's stack. Since we use a custom data structure, the recursion can be paused and resumed at any time

4. A helper function must also be implemented, which will be called again and again during the implementation. This function is called _inorder_left, which adds all left children of a given node to the stack until the node has no left children.

5. When the next() function is called for the first time, the minimum element of the binary search tree must be returned, and then we simulate the recursion and must move forward one step, that is, move to the next minimum element of the binary search tree. The top of the stack always contains the element returned by the next() function. hasNext() is easy to implement since we only need to check if the stack is empty

6. First, given the root node of the binary search tree, we call the function _inorder_left, which ensures that the top of the stack always contains the element returned by the next() function

7. Suppose we call next(), we need to return the next smallest element in the binary search tree, which is the top element of the stack. There are two possibilities: One is that the node at the top of the stack is a leaf node. This is the best case scenario because we don't have to do anything but pop the node off the stack and return its value. So this is a constant time operation. Another case is when the node at the top of the stack owns the right node. We don't need to check the left node because it has already been added to the stack. The top element of the stack either has no left node or the left node has been processed. If there is a right node at the top of the stack, then we need to call the helper function on the right node. The time complexity depends on the structure of the tree

class BSTIterator { Stack<TreeNode> stack; public BSTIterator(TreeNode root) { this.stack = new Stack<TreeNode>();//Use stack to simulate recursion this._leftmostInorder(root);//The algorithm starts with the call of the helper function } //Helper function, add all left child nodes to the stack private void _leftmostInorder(TreeNode root) { while (root != null) { this.stack.push(root); root = root.left; } } public int next() { TreeNode topmostNode = this.stack.pop();//The top element of the stack is the smallest element //Keep the top element of the stack as the smallest element. If the node has a right child, call the help function if (topmostNode.right != null) { this._leftmostInorder(topmostNode.right); } return topmostNode.val; } public boolean hasNext() { return this.stack.size() > 0; } }

class BSTIterator: def __init__(self, root: TreeNode): self.stack = [] #Use stack to simulate recursion self._leftmost_inorder(root) #The algorithm starts with the call of the helper function #Help function, add all left child nodes to the stack def _leftmost_inorder(self, root): while root: self.stack.append(root) root = root.left def next(self) -> int: topmost_node = self.stack.pop() #The top element of the stack is the smallest element #Keep the top element of the stack as the smallest element. If the node has a right child, call the helper function if topmost_node.right: self._leftmost_inorder(topmost_node.right) return topmost_node.val def hasNext(self) -> bool: return len(self.stack) > 0

Time complexity: hasNext(): If there are still elements in the stack, it returns true, otherwise it returns false. So this is an O(1) operation. next(): Contains two main steps. One is to pop an element from the stack, which is the next smallest element. This is an O(1) operation. However, then we have to call the helper function _inorder_left, which needs to be recursive and adds the left node to the stack, which is a linear time operation, O(N) in the worst case. But we only call it on the node containing the right node, and it will not always process N nodes. Only if we have a skewed tree, there will be N nodes. Therefore, the average time complexity of this operation is still O(1), which is in line with the requirements of the problem.

Space complexity: O(h), using a stack to simulate recursion

Given an array of positive integers arr, consider all binary trees that satisfy the following conditions: Each node has 0 or 2 child nodes. The values ​​in the array arr correspond one-to-one to the value of each leaf node in the inorder traversal of the tree. The value of each non-leaf node is equal to the product of the maximum value of the leaf node in its left subtree and right subtree. In all such binary trees, return the smallest possible sum of the values ​​of each non-leaf node

The core of this question is: You must know that in-order traversal determines that all the left elements (including itself) of the k-th element in the arr array (0...n-1) are in the left subtree, and its right elements are all in the right subtree. , and at this time, the product of the maximum values ​​selected from the left and right subtrees is the root at this time, which is the non-leaf node mentioned in the question, so we can assume that from i to j, the minimum sum may be: k at this moment The product sub-problem of the maximum value of the elements on the left and right sides of k is the minimum value of the sub-problem k on the left (i, k), the minimum value of the k-digit right side (k 1, j), That is: dp[i][j]=min(dp[i][j], dp[i][k] dp[k 1][j] max[i][k]*max[k 1][j ]) This question is the same as leetcode1039

class Solution { public int mctFromLeafValues(int[] arr) { int n = arr.length; //Find the maximum value of the elements in arr from i to j, and store it in max[i][j]. i and j can be equal. int[][] max = new int[n][n]; for (int j=0;j<n;j) { int maxValue = arr[j]; for (int i=j;i>=0;i--) { maxValue = Math.max(maxValue, arr[i]); max[i][j] = maxValue; } } int[][] dp = new int[n][n]; for (int j=0; j<n; j ) { for (int i=j; i>=0; i--) { //k is a value between i and j, i<=k<j int min = Integer.MAX_VALUE; for (int k=i; k 1<=j; k ) { min = Math.min(min,dp[i][k] dp[k 1][j] max[i][k]*max[k 1][j]); dp[i][j] = min;//Always maintain the minimum sum between i and j } } } return dp[0][n-1]; } }

class Solution: def mctFromLeafValues(self, arr: List[int]) -> int: n = len(arr) dp = [[float('inf') for _ in range(n)] for _ in range(n)] # Set the initial value to the maximum maxval = [[0 for _ in range(n)] for _ in range(n)] # Set the initial range query maximum value to 0 for i in range(n):# Find the largest element in the interval [i, j] for j in range(i, n): maxval[i][j] = max(arr[i:j 1]) for i in range(n):# Leaf nodes do not participate in calculation dp[i][i] = 0 for l in range(1, n): # Enumeration interval length for s in range(n - l): # Enumerate the starting point of the range for k in range(s, s l):# Enumerate and divide two subtrees, k is a value in the middle between s and l dp[s][s l] = min(dp[s][s l], dp[s][k] dp[k 1][s l] maxval[s][k] * maxval[k 1][s l]) return dp[0][n - 1]

Time: O(n^3), Space: O(n^2)

1. If you want to minimize the mct value, then the leaf nodes with smaller values ​​should be placed at the bottom as much as possible, and the leaf nodes with larger values ​​should be placed as high as possible. Because the leaf nodes at the bottom are used for multiplication more times. This determines that we need to find a minimum value. You can find a minimum value by maintaining a monotonically decreasing stack, because since it is a monotonically decreasing stack, the node on the left must be greater than the node on the top of the stack, and the current node (on the right) is also greater than the node on the top of the stack (because the current node is smaller than the top of the stack) , it is pushed directly into the stack)

2. After finding this minimum value, you need to look left and right to see which value is smaller on the left or right. The purpose is to put the smaller value at the bottom as much as possible.

class Solution { public int mctFromLeafValues(int[] arr) { Stack<Integer> st = new Stack(); st.push(Integer.MAX_VALUE); int mct = 0; //Start to construct a decreasing stack. If the current element is greater than the element on the top of the stack, the element on the top of the stack will be popped out of the stack to find the minimum value. for (int i = 0; i < arr.length; i ) { while (arr[i] >= st.peek()) { //The top element of the stack is popped out of the stack and combined with the smaller elements on the left and right sides mct = st.pop() * Math.min(st.peek(), arr[i]); } st.push(arr[i]); } while (st.size() > 2) { mct = st.pop() * st.peek(); } return mct; } }

class Solution: def mctFromLeafValues(self, A: List[int]) -> int: res, n = 0, len(A) stack = [float('inf')] #Put the maximum value first on the stack #Start to construct a decreasing stack. If the current element is greater than the top element of the stack, the top element of the stack will be popped out of the stack. The minimum value can be found. for a in A: while a >= stack[-1]: mid = stack.pop() #The top element of the stack is popped out of the stack and combined with the smaller elements on the left and right sides res = mid * min(stack[-1], a) stack.append(a) while len(stack) > 2: res = stack.pop() * stack[-1] return res

Time: O(n), Space: O(n)

Convert an ordered array in ascending order into a height-balanced binary search tree. A height-balanced binary tree means that the absolute value of the height difference between the left and right subtrees of each node of a binary tree does not exceed 1.

1. Select the middle number as the root node of the binary search tree, so that the number of numbers assigned to the left and right subtrees is the same or only differs by 1, which can keep the tree balanced.

2. After determining the root node of the balanced binary search tree, the remaining numbers are located in the left subtree and right subtree of the balanced binary search tree respectively. The left subtree and the right subtree are also balanced binary search trees respectively, so it can Create a balanced binary search tree recursively

3. Why can such an achievement be guaranteed to be "balanced"? Here you can refer to "1382. Balance the binary search tree"

4. The basic situation of recursion is that the balanced binary search tree does not contain any numbers. At this time, the balanced binary search tree is empty.

5. In the case of a given in-order traversal sequence array, the numbers in each subtree must be continuous in the array. The numbers contained in the subtree can be determined by the array subscript range. The subscript range is marked as [left, right], when left>right, the balanced binary search tree is empty

class Solution: def sortedArrayToBST(self, nums: List[int]) -> TreeNode: def helper(left, right): if left > right: #Dichotomy termination condition return None mid = (left right) // 2 #Always select the number to the left of the middle position as the root node root = TreeNode(nums[mid]) #First determine the root node, then recurse the left and right subtrees root.left = helper(left, mid - 1) root.right = helper(mid 1, right) return root return helper(0, len(nums) - 1)

Time complexity: O(n), where n is the length of the array. Visit each number only once

Space complexity: O(logn), where n is the length of the array. The space complexity does not consider the return value, so the space complexity mainly depends on the depth of the recursive stack. The depth of the recursive stack is O(logn)

Time: O(n), Space: O(n)

1. Set left closed and right open intervals

2. Use the fast and slow pointers to find the median

3. Recursively construct the tree

class Solution: def sortedListToBST(self, head: ListNode) -> TreeNode: def getMedian(left: ListNode, right: ListNode) -> ListNode: fast=slow=left while fast != right and fast.next != right:#Define the interval as left closed and right open fast = fast.next.next#The fast pointer moves twice and the slow pointer moves once slow = slow.next return slow #The slow pointer is the median at this time def buildTree(left: ListNode, right: ListNode) -> TreeNode: if left == right: return None mid = getMedian(left, right) #The interval is left closed and right open root = TreeNode(mid.val) #First determine the root node, then construct the left and right subtrees root.left = buildTree(left, mid) #No need for mid.pre root.right = buildTree(mid.next, right) return root return buildTree(head, None)

Time complexity: O(nlogn), where n is the length of the linked list. Assume that the time to construct a binary search tree from a linked list of length n is T(n), and the recurrence formula is T(n)=2⋅T(n/2) O(n). According to the main theorem, T(n)= O(nlogn)

Space complexity: O(logn), only the space other than the returned answer is calculated here. The height of the balanced binary tree is O(logn), which is the maximum depth of the stack during the recursive process, which is the required space.

1. Assume that the left endpoint number of the current linked list is left, the right endpoint number is right, the inclusion relationship is "double-closed", the number of the linked list nodes is [0, n), and the order of in-order traversal is "left subtree - root node - Right subtree", then in the process of divide and conquer, we don't have to rush to find the median node of the linked list, but use a placeholder node, and then fill in its value when the node is traversed in in-order

2. Perform mid-order traversal by calculating the number range: the number corresponding to the median node is mid=(left right 1)/2, and the number ranges corresponding to the left and right subtrees are [left, mid−1] and [mid 1 respectively. ,right], if left>right, then the traversed position corresponds to an empty node, otherwise it corresponds to a node in the binary search tree

3. We already know the structure of this binary search tree, and the question gives its in-order traversal result. Then we only need to perform an in-order traversal on it to restore the entire binary search tree.

4. Recursive process diagram

class Solution: def sortedListToBST(self, head: ListNode) -> TreeNode: def getLength(head: ListNode) -> int: ret = 0 while head: ret=1 head = head.next return ret def buildTree(left: int, right: int) -> TreeNode: if left > right: #End condition of mid-order traversal return None mid = (left right 1) // 2 root = TreeNode() #Use inorder traversal, first construct the left subtree, then return to the root node, and then construct the right subtree, starting from the first element root.left = buildTree(left, mid - 1) nonlocal head #can modify the outer non-global variable head root.val = head.val #Start assigning values ​​from the first node head = head.next root.right = buildTree(mid 1, right) return root length = getLength(head) return buildTree(0, length - 1)

Time complexity: O(n), where n is the length of the linked list. Assume that the time to construct a binary search tree from a linked list of length n is T(n), and the recurrence formula is T(n)=2⋅T(n/2) O(1). According to the main theorem, T(n)= O(n)

Space complexity: O(logn), only the space other than the returned answer is calculated here. The height of the balanced binary tree is O(logn), which is the maximum depth of the stack during the recursive process, which is the required space.

Serialization is the operation of converting a data structure or object into continuous bits. The converted data can then be stored in a file or memory, and can also be transmitted to another computer environment through the network and reconstructed in the opposite way. Get the original data. Please design an algorithm to implement serialization and deserialization of binary trees. Your sequence/deserialization algorithm execution logic is not limited here. You only need to ensure that a binary tree can be serialized into a string and deserialize the string into the original tree structure.

1. Serialization

2.Deserialization

class Codec: def serialize(self, root): #Preorder traversal implements serialization if root == None: return 'X,' leftserilized = self.serialize(root.left) rightserilized = self.serialize(root.right) return str(root.val) ',' leftserilized rightserilized def deserialize(self, data): data = data.split(',') root = self.buildTree(data) return root def buildTree(self, data): val = data.pop(0) #Pop the first character if val == 'X': return None #Return empty node node = TreeNode(val) node.left = self.buildTree(data) node.right = self.buildTree(data) return node

Time: O(n), Space: O(n)

Given the root nodes p and q of two binary trees, write a function to check whether the two trees are the same

1. If both binary trees are empty, then the two binary trees are the same. If one and only one of the two binary trees is empty, then the two binary trees must not be the same

2. If both binary trees are not empty, then first determine whether the values ​​of their root nodes are the same. If they are not the same, the two binary trees must be different. If they are the same, then determine whether the left subtrees and right subtrees of the two binary trees are the same. subtrees are the same. This is a recursive process, so you can use depth-first search to recursively determine whether two binary trees are the same.

class Solution: def isSameTree(self, p: TreeNode, q: TreeNode) -> bool: if not p and not q: #Both trees are empty and the same return True elif not p or not q: #Only one of the trees is empty, the two trees are not the same return False elif p.val != q.val: return False else: return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Time complexity: O(\min(m,n))O(min(m,n)), where mm and n are the number of nodes of the two binary trees respectively. Perform a depth-first search on two binary trees at the same time. The node will be accessed only when the corresponding nodes in the two binary trees are not empty, so the number of nodes visited will not exceed the number of nodes in the smaller binary tree.

Space complexity: O(\min(m,n))O(min(m,n)), where mm and n are the number of nodes of the two binary trees respectively. The space complexity depends on the number of levels of recursive calls. The number of levels of recursive calls will not exceed the maximum height of the smaller binary tree. In the worst case, the height of the binary tree is equal to the number of nodes.

1. First determine whether the two binary trees are empty. If both binary trees are not empty, start the breadth-first search from the root nodes of the two binary trees.

2. Use two queues to store the nodes of two binary trees respectively. Initially, the root nodes of the two binary trees are added to the two queues respectively. Each time, one node is taken out from the two queues and the following comparison operation is performed. Compare the values ​​of two nodes. If the values ​​of the two nodes are not the same, the two binary trees must be different; If the values ​​of two nodes are the same, determine whether the child nodes of the two nodes are empty. If only the left child node of one node is empty, or the right child node of only one node is empty, the structures of the two binary trees are different. Therefore the two binary trees must be different; If the structures of the child nodes of the two nodes are the same, add the non-empty child nodes of the two nodes to the two queues respectively. You need to pay attention to the order when adding the child nodes to the queue. If the left and right child nodes are not empty, add the left child node first. , then add the right child node

3. If both queues are empty at the same time at the end of the search, the two binary trees are the same. If only one queue is empty, the structure of the two binary trees is different, so the two binary trees are different

class Solution: def isSameTree(self, p: TreeNode, q: TreeNode) -> bool: if not p and not q: #Both trees are empty and the same return True if not p or not q: #Only one of the trees is empty, the two trees are not the same return False queue1 = collections.deque([p]) queue2 = collections.deque([q]) while queue1 and queue2: node1 = queue1.popleft() node2 = queue2.popleft() if node1.val != node2.val: return False left1, right1 = node1.left, node1.right left2, right2 = node2.left, node2.right if (not left1) ^ (not left2): # ^ means XOR, if they are different, they are 1, if they are the same, they are 0 return False if (not right1) ^ (not right2): return False if left1: #Enter the node into the queue when it is not empty queue1.append(left1) if right1: queue1.append(right1) if left2: queue2.append(left2) if right2: queue2.append(right2) return not queue1 and not queue2

Time complexity: O(\min(m,n))O(min(m,n)), where mm and n are the number of nodes of the two binary trees respectively. Perform a breadth-first search on two binary trees at the same time. The node will be accessed only when the corresponding nodes in the two binary trees are not empty, so the number of nodes visited will not exceed the number of nodes in the smaller binary tree.

Space complexity: O(\min(m,n))O(min(m,n)), where mm and n are the number of nodes of the two binary trees respectively. The space complexity depends on the number of elements in the queue. The number of elements in the queue will not exceed the number of nodes of the smaller binary tree.

1. For any tree, the form of preorder traversal is always [Root node, [result of preorder traversal of left subtree], [result of preorder traversal of right subtree]] That is, the root node is always the first node in the preorder traversal. The form of inorder traversal is always [ [In-order traversal result of left subtree], root node, [In-order traversal result of right subtree] ]

2. As long as we locate the root node in the in-order traversal, then we can know the number of nodes in the left subtree and right subtree respectively. Since the lengths of pre-order traversal and in-order traversal of the same subtree are obviously the same, we can correspond to the results of the pre-order traversal and locate all the left and right brackets in the above form.

3. In this way, we know the results of the pre-order traversal and in-order traversal of the left subtree, and the results of the pre-order traversal and in-order traversal of the right subtree. We can recursively construct the left subtree and the right subtree. tree, and then connect these two subtrees to the left and right positions of the root node

4. Optimization: When locating the root node in in-order traversal, a simple method is to directly scan the entire in-order traversal result and find the root node list.index(x), but the time complexity of doing so is relatively high. high. We can consider using a HashMap to help us quickly locate the root node. For each key-value pair in the hash map, the key represents an element (the value of the node) and the value represents its occurrence position in the in-order traversal. Before constructing the binary tree, we can scan the list traversed in order once to construct this hash map. In the subsequent process of constructing the binary tree, we only need O(1) time to locate the root node.

1. Officially optimized, but there are many parameters. You can use two parameters. See the combination of post-order and mid-order.

2. Simple version

Time complexity: O(n), where n is the number of nodes in the tree

Space complexity: O(n), in addition to the O(n) space required to return the answer, we also need to use O(n) space to store the hash map, and O(h) (where h is the height of the tree ) space represents the stack space during recursion

1. We use a stack and a pointer to assist in the construction of the binary tree. Initially, the root node (the first node of the pre-order traversal) is stored in the stack, and the pointer points to the first node of the in-order traversal "the final node reached by the current node continuously moving to the left."

2. Enumerate each node in the preorder traversal except the first node. If index happens to point to the top node of the stack, then we continuously pop the top node of the stack and move index to the right, and use the current node as the right child of the last popped node

3. If index is different from the top node of the stack, we use the current node as the left son of the top node of the stack.

4. No matter what the situation is, we will finally push the current node onto the stack

class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode: if not preorder: return None root = TreeNode(preorder[0]) stack = [root] inorderIndex = 0 #The final node reached by the current node continuously moving to the left, consistent with in-order traversal for i in range(1, len(preorder)):#Traverse preorder traversal starting from the second node preorderVal = preorder[i] node = stack[-1] #The top node of the stack if node.val != inorder[inorderIndex]: #When the top node of the stack is not equal, it is the left child node.left = TreeNode(preorderVal) #Construct the left child directly stack.append(node.left) #Push the left child onto the stack else: #When the top nodes of the stack are equal, it has been traversed to the leftmost point, and it needs to be popped out of the stack and then traversed to the right child of a certain node. while stack and stack[-1].val == inorder[inorderIndex]: node = stack.pop() #The top element of the stack is popped out of the stack inorderIndex = 1 #Replace the leftmost element node.right = TreeNode(preorderVal) #When the two are different, the parent node of the current element is found stack.append(node.right) #Also push the current element onto the stack return root

Time complexity: O(n), where n is the number of nodes in the tree

Space complexity: O(n). In addition to the O(n) space required for the returned answer, we also need to use O(h) (where h is the height of the tree) space to store the stack.

1. The last element of the array traversed in post-order represents the root node, and then divided into in-order traversals.

2. Note that there is a dependency relationship where you need to create the right subtree first and then the left subtree. It can be understood that in the array of post-order traversal, the entire array first stores the nodes of the left subtree, then the nodes of the right subtree, and finally the root node. If you select "the last node of post-order traversal" as the root each time node, the first constructed one should be the right subtree

1.Official: two parameters

2. Simple version

Time complexity: O(n), where n is the number of nodes in the tree

Space complexity: O(n), in addition to the O(n) space required to return the answer, we also need to use O(n) space to store the hash map, and O(h) (where h is the height of the tree ) space represents the stack space during recursion

1. If you reverse the in-order traversal, you will get a reverse in-order traversal, that is, traverse the right child each time, then traverse the root node, and finally traverse the left child. If you reverse the post-order traversal, you get the reverse pre-order traversal, that is, traverse the root node each time, then traverse the right child, and finally traverse the left child.

2. The difference from the previous question is: all left children become right children, all right children become left children, and forward order traversal is changed to reverse order traversal.

class Solution: def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode: if not postorder: return None root = TreeNode(postorder[-1]) stack = [root] inorderIndex = -1 #The final node reached by the current node continuously moving to the right, consistent with in-order traversal for i in range(len(postorder)-2, -1,-1):#Traverse post-order traversal starting from the penultimate node postorderVal = postorder[i] node = stack[-1] #The top node of the stack if node.val != inorder[inorderIndex]: #When the top node of the stack is not equal, it is the right child node.right = TreeNode(postorderVal) #Construct the right child directly stack.append(node.right) #Push the right child onto the stack else: #When the top nodes of the stack are equal, it has been traversed to the rightmost point. It needs to be popped out of the stack and then traversed to the left child of a certain node. while stack and stack[-1].val == inorder[inorderIndex]: node = stack.pop() #The top element of the stack is popped out of the stack inorderIndex -= 1 #Replace the rightmost element node.left = TreeNode(postorderVal) #When the two are different, the parent node of the current element is found stack.append(node.left) #Also push the current element onto the stack return root

Time complexity: O(n), where n is the number of nodes in the tree

Space complexity: O(n). In addition to the O(n) space required for the returned answer, we also need to use O(h) (where h is the height of the tree) space to store the stack.

A path is defined as a sequence starting from any node in the tree, connecting along the parent node-child node, and reaching any node. The same node appears at most once in a path sequence. The path contains at least one node and does not necessarily pass through the root node. The path sum is the sum of the values ​​of each node in the path. Give you the root node root of a binary tree and return its maximum path sum

1. First, consider implementing a simplified function maxGain(node), which calculates the maximum contribution value of a node in the binary tree. Specifically, it searches for the node as the starting point in the subtree with the node as the root node. a path that maximizes the sum of node values ​​on the path

2. Specifically, the function is calculated as follows. The maximum contribution value of an empty node is equal to 00. The maximum contribution value of a non-empty node is equal to the sum of the node value and the maximum contribution value in its child nodes (for leaf nodes, the maximum contribution value is equal to the node value

3. The above calculation process is a recursive process. Therefore, by calling the function maxGain on the root node, the maximum contribution value of each node can be obtained.

4. After getting the maximum contribution value of each node according to the function maxGain, how to get the maximum path sum of the binary tree? For a node in a binary tree, the maximum path sum of the node depends on the value of the node and the maximum contribution value of the left and right child nodes of the node. If the maximum contribution value of the child node is positive, it is included in the maximum path sum of the node. , otherwise it will not be included in the maximum path sum of the node. Maintain a global variable maxSum to store the maximum path sum, and update the value of maxSum during the recursive process. The final value of maxSum is the maximum path sum in the binary tree.

class Solution: def __init__(self): self.maxSum = float("-inf") #The maximum value is initialized to negative infinity def maxPathSum(self, root: TreeNode) -> int: def maxGain(node): #Get the maximum contribution value of the node if not node: return 0 # Recursively calculate the maximum contribution value of the left and right child nodes # Only when the maximum contribution value is greater than 0, the corresponding child node will be selected leftGain = max(maxGain(node.left), 0) rightGain = max(maxGain(node.right), 0) # First get the maximum path value with the current node as the root node, and then return the maximum contribution value of the node #The maximum path sum of a node depends on the value of the node and the maximum contribution value of the left and right child nodes of the node priceNewpath = node.val leftGain rightGain self.maxSum = max(self.maxSum, priceNewpath) # Update answer # Return the maximum contribution value of the node, which is determined by the larger of the node value and the left subtree/right subtree return node.val max(leftGain, rightGain) maxGain(root) return self.maxSum

Time complexity: O(N)O(N), where NN is the number of nodes in the binary tree. No more than 2 visits to each node

Space complexity: O(N)O(N), where NN is the number of nodes in the binary tree. The space complexity mainly depends on the number of recursive call levels. The maximum number of levels is equal to the height of the binary tree. In the worst case, the height of the binary tree is equal to the number of nodes in the binary tree.

Given an integer array nums without duplicate elements. A maximum binary tree constructed directly and recursively from this array is defined as follows: The root of the binary tree is the largest element in the array nums. The left subtree is the largest binary tree constructed recursively through the left part of the maximum value in the array. The right subtree is the largest binary tree constructed recursively through the right part of the maximum value in the array. Returns the largest binary tree constructed with the given array nums

Still a trilogy 1. Recursion termination condition: When the arrays of the left subtree and the right subtree are both empty 2. What this recursion does: Take out the maximum value of the array, divide the array into left and right arrays based on the maximum value, and then perform recursive assignment 3. What is returned: The root node of the subtree

class Solution: def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode: if not nums: return None # Applicable when there are repeated elements # max_v, m_i = float(-inf), 0 # for i, v in enumerate(nums): # if v>max_v: # max_v = v # m_i = i max_v = max(nums) m_i = nums.index(max_v) root = TreeNode(max_v) root.left = self.constructMaximumBinaryTree(nums[:m_i]) root.right = self.constructMaximumBinaryTree(nums[m_i 1:]) return root

Time complexity: O(n^2), method construct is called n times in total. Each time you recursively search for the root node, you need to traverse all elements in the current index range to find the maximum value. In general, the complexity of each traversal is O(logn), and the total complexity is O(nlogn). In the worst case, the array numsnums is sorted, and the total complexity is O(n^2)

Space complexity: O(n)O(n). The recursive call depth is nn. On average, the recursive call depth for an array of length n is O(logn)

1. Construct a decreasing stack and push it into the stack in sequence. If the element on the top of the stack is smaller than the current element, the element on the top of the stack is popped off the stack.

2. Compare the size of the top element after being popped from the stack with the size of the current element. If it is larger than the current element, the current element is used as the parent node, and the popped element is used as the left child; if the top element of the stack is smaller than the current element, the top element of the stack is used as the parent node. And pop it off the stack. The previously popped element is used as the right child, and continues until the current node is pushed onto the stack.

3. Until the end of the last element, a decreasing stack is formed, and the stack is popped sequentially. The popped elements are used as the right children. The last one popped out of the stack is the root node. Return to this node.

Example

public TreeNode constructMaximumBinaryTree(int[] nums) { TreeNode root = null, node = null; LinkedList<TreeNode> stack = new LinkedList<>(); for (int i = 0; i < nums.length; i) { node = new TreeNode(nums[i]); //Construct a decreasing stack. When the top element of the stack is smaller than the current element, the top element of the stack will be popped off the stack. while (!stack.isEmpty() && stack.peek().val < node.val) { root = stack.pop();//The top element of the current stack, the smallest value //Compare the size of the top of the stack after popping with the size of the current element. If it is larger than the current element, the current element will be used as the parent node. if (stack.isEmpty() || stack.peek().val > node.val) { node.left = root; } else {//If it is less than the current element, the top element of the stack will be used as the parent node stack.peek().right = root; } } stack.push(node);//Push the current element onto the stack } // The decrementing stack is completely formed and can be popped out of the stack as the right child. while (!stack.isEmpty()) { root = stack.pop(); if (!stack.isEmpty()) { stack.peek().right = root; } } return root;//The last thing to pop off the stack is root, return to this node }

Time complexity: O(n), Space complexity: O(n)

Maximum tree definition: A tree in which the value of each node is greater than any other value in its subtree gives the root node root of the largest tree. Like the previous question, the given tree is constructed recursively from the list A, we are not given A directly, only a root node root, assuming B is a copy of A with the value val appended to the end. The question data guarantees that the values ​​in B are different. Return Construct(B)

Each time it is compared with the head node, if it is smaller, its right node is checked. Update: 1) The existing node becomes the left node of the new node, 2) the new node becomes the right node of the parent node

def insertIntoMaxTree(self, root: TreeNode, val: int) -> TreeNode: # dummy dummy variable, its right child points to the root node dummy = TreeNode(0) dummy.right = root # search If the current root node value is greater than val, continue to query its right child p, c = dummy, dummy.right while c and c.val > val: p, c = c, c.right # insert At this time, val is greater than the root node, val is used as the right child of the previous root node, and the current root node is used as the left child of val n = TreeNode(val) p.right = n n.left = c return dummy.right #dummy has not changed, its right child points to the root node

The same processing is done when it is greater than the root node. When it is less than the root node, the right child of the root node is processed recursively.

def insertIntoMaxTree(self, root: TreeNode, val: int) -> TreeNode: if root is None: # Recursive termination condition returnTreeNode(val) if val > root.val: #How to handle val greater than the current root node tmp = TreeNode(val) tmp.left = root return tmp # Recursively process the right child of the root node root.right = self.insertIntoMaxTree(root.right, val) return root # Recursive return value, root node

Given a binary tree, determine whether it is a height-balanced binary tree. In this question, a height-balanced binary tree is defined as: the absolute value of the height difference between the left and right subtrees of each node of a binary tree does not exceed 1

1. Define the function height, which is used to calculate the height of any node p in the binary tree.

2. Similar to the pre-order traversal of a binary tree, that is, for the currently traversed node, first calculate the height of the left and right subtrees. If the height difference between the left and right subtrees does not exceed 1, then recursively traverse the left and right subnodes respectively, and determine the left and right subtrees. Whether the subtree and the right subtree are balanced. This is a top-down recursive process

class Solution: #Top-down, similar to pre-order traversal, will repeatedly calculate the height of the left and right subtrees def isBalanced(self, root: TreeNode) -> bool: def height(root: TreeNode) -> int: if not root: return 0 return max(height(root.left), height(root.right)) 1 if not root: return True return abs(height(root.left) - height(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)

Time complexity: O(n), where n is the number of nodes in the binary tree. Using bottom-up recursion, the calculation height of each node and the judgment of whether it is balanced only need to be processed once. In the worst case, all nodes in the binary tree need to be traversed, so the time complexity is O(n)

Space complexity: O(n), where n is the number of nodes in the binary tree. The space complexity mainly depends on the number of levels of recursive calls. The number of levels of recursive calls will not exceed nn.

1. Since method one is top-down recursive, the function \texttt{height}height will be called repeatedly for the same node, resulting in high time complexity. If the bottom-up approach is used, the function \texttt{height}height will only be called once for each node.

2. The bottom-up recursive approach is similar to post-order traversal. For the currently traversed node, first recursively determine whether its left and right subtrees are balanced, and then determine whether the subtree rooted at the current node is balanced. If a subtree is balanced, its height is returned (the height must be a non-negative integer), otherwise -1−1 is returned. If there is an unbalanced subtree, the entire binary tree must be unbalanced

class Solution: #Bottom-up, similar to post-order traversal, first determine the left and right subtrees, and then determine the root node, ensuring that the height of each node is only calculated once def isBalanced(self, root: TreeNode) -> bool: def height(root: TreeNode) -> int: if not root: return 0 leftHeight = height(root.left) rightHeight = height(root.right) if leftHeight == -1 or rightHeight == -1 or abs(leftHeight - rightHeight) > 1: return -1 else: return max(leftHeight, rightHeight) 1 return height(root) >= 0

Time complexity: O(n), where n is the number of nodes in the binary tree. Using bottom-up recursion, the calculation height of each node and the judgment of whether it is balanced only need to be processed once. In the worst case, all nodes in the binary tree need to be traversed, so the time complexity is O(n)

Space complexity: O(n), where n is the number of nodes in the binary tree. The space complexity mainly depends on the number of levels of recursive calls. The number of levels of recursive calls will not exceed nn.

Given a binary tree, find its minimum depth. The minimum depth is the number of nodes on the shortest path from the root node to the nearest leaf node

1. The key to this question is to figure out the recursive end condition The definition of a leaf node is that when both the left child and the right child are null, it is called a leaf node. When the left and right children of the root node are empty, return 1 When one of the left and right children of the root node is empty, return the depth of the child node that is not empty. When both the left and right children of the root node are empty, return the node values ​​of the smaller depth of the left and right children.

class Solution: def minDepth(self, root: TreeNode) -> int: if not root: return 0 #When both the left and right subtrees are empty, it is a leaf node, and the return distance is 1 if not root.left and not root.right: return 1 min_depth = 10**9 if root.left: #The left subtree exists, compare the minimum distance of the left subtree with the current minimum distance min_depth = min(self.minDepth(root.left), min_depth) if root.right: min_depth = min(self.minDepth(root.right), min_depth) return min_depth 1

Time complexity: O(n), where n is the number of nodes in the tree. Visit each node once

Space complexity: O(h), where h is the height of the tree. The space complexity mainly depends on the overhead of stack space during recursion. In the worst case, the tree appears in a chain shape and the space complexity is O(n). On average, the height of the tree is positively related to the logarithm of the number of nodes, and the space complexity is O(logN)

When we find a leaf node, we directly return the depth of the leaf node. The nature of breadth-first search ensures that the depth of the leaf node searched first must be the smallest.

class Solution: def minDepth(self, root: TreeNode) -> int: if not root: return 0 que = collections.deque([(root, 1)]) while que: node, depth = que.popleft() #The first leaf node must be the closest leaf node if not node.left and not node.right: return depth if node.left: que.append((node.left, depth 1)) if node.right: que.append((node.right, depth 1)) return 0

Time complexity: O(n), where n is the number of nodes in the tree. Visit each node once

Space complexity: O(n), where n is the number of nodes in the tree. The space complexity mainly depends on the overhead of the queue. The number of elements in the queue will not exceed the number of nodes in the tree.

The definition of dp[i] is: the Fibonacci value of the i-th number is dp[i]

State transition equation dp[i] = dp[i - 1] dp[i - 2]

The question also directly gives us how to initialize dp[0] = 0;dp[1] = 1;

dp[i] depends on dp[i - 1] and dp[i - 2], so the order of traversal must be from front to back.

When N is 10, the dp array should be the following sequence: 0 1 1 2 3 5 8 13 21 34 55 If you write the code and find that the result is wrong, print out the dp array to see if it is consistent with the sequence we derived.

There is one way to climb the stairs to the first floor, and there are two ways to climb the stairs to the second floor. Then take two more steps on the first flight of stairs to reach the third floor, and one more step on the second flight of stairs to reach the third floor. So the state of the stairs to the third floor can be deduced from the state of the stairs to the second floor and the state of the stairs to the first floor, then you can think of dynamic programming.

dp[i]: There are dp[i] ways to climb to the i-th staircase

It can be seen from the definition of dp[i] that dp[i] can be derived in two directions. The first is dp[i - 1]. There are dp[i - 1] ways to go up the i-1 stairs. Then jumping one step at a time is dp[i]. There is also dp[i - 2]. There are dp[i - 2] ways to go up the i-2 stairs. Then jumping two steps in one step is dp[i]. Then dp[i] is the sum of dp[i - 1] and dp[i - 2]! So dp[i] = dp[i - 1] dp[i - 2]

So if i is 0, what should dp[i] be? There are many explanations for this, but they are basically explained directly towards the answer.

For example, there is a way to force yourself to comfort yourself and climb to the 0th floor. Doing nothing is also a way: dp[0] = 1, which is equivalent to standing directly on the top of the building.

I thought that when I ran to floor 0, the method was 0. I could only walk one or two steps at a time. However, the floor was 0 and I just stood on the roof. There was no method, so dp[0] should be 0.

Most of the reasons why dp[0] should be 1 are actually because if dp[0]=1, i can pass the problem by starting from 2 during the recursion process, and then rely on the result to explain dp[0 ] = 1

The question says that n is a positive integer, but the question does not say that n is 0 at all. Therefore, this question should not discuss the initialization of dp[0].

My principle is: do not consider the initialization of dp[0], only initialize dp[1] = 1, dp[2] = 2, and then start recursion from i = 3, so that it meets the definition of dp[i]

It can be seen from the recursive formula dp[i] = dp[i - 1] dp[i - 2]; that the traversal order must be from front to back.

When N is 10, the dp array should be the following sequence: 0 1 1 2 3 5 8 13 21 34 55