zero
The LeetCode tree lifting program has been going on for a few days.
Today, I will make a brief summary of the progress of “tree”. How is it going with my dear friends in the group? I expect that in the whole “tree” stage, there will be four summaries and a complete double disc, so there should be five summary materials.
The distribution is as follows:
- The basic traversal of the “tree” focuses on the recursive understanding of the “tree”
- Module 1: Basic traversal, marking the brushes in LeetCode
- Module 2: Traversing variants – top down, explaining and coding these topics
- Module 3: Traversing variants – non-top down, also explaining and coding these topics
- Final review summary “Most Important”
Let’s list our plans:
So, today will be the first order, order, follow up, hierarchical traversal basic code writing
Today’s content is relatively easy, is “tree” four kinds of traversal. But, again, take a look at recursion, take a look at recursion, take a look at recursion, take a look at recursion, because that’s basically the logic behind most of these problems.
After the basic use of Python to carry out the logical implementation of the code, relatively easy and popular, after all, the algorithm is to learn the idea, as to how to achieve, any language can reproduce it, right
Today is the “tree” traversal, let’s define a tree structure class, and a complete binary tree!
# Tree class
class TreeNode:
def __init__(self, value) :
self.value = value
self.left = None
self.right = None
Copy the codeConstruct a complete binary tree:
if __name__ == "__main__":
# Create new node
root = TreeNode('A')
node_B = TreeNode('B')
node_C = TreeNode('C')
node_D = TreeNode('D')
node_E = TreeNode('E')
node_F = TreeNode('F')
node_G = TreeNode('G')
node_H = TreeNode('H')
node_I = TreeNode('I')
# Build binary tree
# A
# / \
# B C
# / \ / \
# D E F G
# / \
# H I
root.left, root.right = node_B, node_C
node_B.left, node_B.right = node_D, node_E
node_C.left, node_C.right = node_F, node_G
node_D.left, node_D.right = node_H, node_I
Copy the codeFirst, a quick reminder:
Today’s code will use stacks or queues to help with implementation, but in Python, we use lists
# stack
stack = []
# stack - press the stack
stack.append('nodes')
# stack - Pops the top element of the stack
stack.pop()
# queue
queue = []
# Stack - join queue
queue.append('nodes')
# Stack - out of queue
queue.pop(0)
Copy the codeThe dessert
It’s sweet. Try to understand recursion
Recursion is not easy for many people to understand, especially if you are a student, or if you are a beginner. In fact, many people who have worked for several years are not easy to understand recursion, and recursion is sometimes very difficult to explain, you have to think clearly to really translate into a thinking logic of your own.
Here I want to try to say, can you say clearly, cough, try…
Let’s use the following traversal example here, other recursion way their own brain understand ha!
Core code (code 1, 2, 3, 4 below for each line) :
def post_order_traverse(root) :code1 | if not root: returncode2| post_order_traverse (root left) code3| post_order_traverse (root. Right) code4 | print(root.value, end="")
Copy the codeWhen executing step 1 in the figure, code 1 and code 2 must have been executed. Recursive call to the end, judge node H is null, execute if not root: return, then execute code 4, the node H is printed out.
Similarly, when executing step 2 in the figure, it is the same logic, recursive call, judge that both children are null, return directly, and then print out node I.
And then up, node H and node I are printed and after they return, we go back and print node D
And so on…
one
The first sequence traversal
Recursive traversal procedure:
A. Access the root node.
B. Preorder traversal of its left subtree;
C. The right subtree is traversed first;
And then you recurse all the way down, and when you access the node, you can do something about the node, like simply access the value of the node
Below is a binary tree, let’s manually simulate the traversal process
According to the description in the figure above, we can get a preordered traversal process according to the order, and get the preordered traversal sequence:
A B D H I E C F G
Copy the codeTo reproduce the above logic:
class Solution:
def pre_order_traverse(self, root) :
if not root:
return
print(root.value, end="")
self.pre_order_traverse(root.left)
self.pre_order_traverse(root.right)
Copy the codeIn the whole recursion, the seemingly neat, very readable 3 lines of code, in fact, for beginners, the brain to understand its implementation process is more difficult!
If not too clear, suggest in-depth understanding of the above to the [dessert], attentively understand, do not understand the group can directly discuss ha!
Let’s look at the non-recursive traversal again:
A. Access the root node. B. Determine if there is a right child, if there is a right child, press the stack C. Determine if there is a left child, if there is a left child, access it, otherwise, pop the top element of the stack D. Loop through 2 and 3
In non-recursive traversal, the key is to use the stack to implement the idea of pushing the nodes to be accessed later, first traversing the root node, then pushing the right child, and finally accessing the left child
class Solution:
def pre_order_traverse_no_recursion(self, root) :
if not root:
return
stack = [root]
while stack:
print(root.value, end="") # Access the root node
if root.right:
stack.append(root.right) # Determine if there is a right child, if there is a right child, press the stack
if root.left: If there is a left child, access it, otherwise, pop the top element on the stack
root = root.left
else:
root = stack.pop()
Copy the codeThis idea is also a variant of recursion, which defines the stack used in recursion.
two
In the sequence traversal
Let’s do the recursive implementation first
A. Preorder traversal of its left subtree;
B. Access the root node.
C. The right subtree is traversed first;
And then you recurse all the way down, and when you access the node, you can do something about the node, like simply access the value of the node
Below is a binary tree, let’s manually simulate the order traversal process
According to the recursion process of the ordered traversal above, the sequence of the ordered traversal in is obtained:
H D I B E A F C G
Copy the codeLet’s continue to reproduce this logic in Python:
class Solution:
def in_order_traverse(self, root) :
if not root:
return
self.in_order_traverse(root.left)
print(root.value, end="")
self.in_order_traverse(root.right)
Copy the codeIt is similar to preorder traversal, except that the print statement of the node to be accessed is transposed.
Let’s take a look at the non-recursive procedure of ordering traversal in:
A. When traversing a node, push the stack and continue traversing its left subtree; B. When the left subtree traversal is complete, pop the top element (the last element in the left subtree) from the top of the stack and access it; C. Finally, proceed with the sequence traversal according to the currently corrected right child. If there is no right child, continue to pop the top element of the stack.
class Solution:
def in_order_traverse_no_recursion(self, root) :
if not root:
return
stack = []
while stack or root:
while root:
stack.append(root)
root = root.left
if stack:
tmp = stack.pop()
print(tmp.value, end="")
root = tmp.right
Copy the codeI believe the above 3 steps are clear enough, but let’s put it in more plain language:
Sequence traversal of the recursive process is also use a “stack” to implement, because it is in the sequence traversal, you should first visit to the left child, and must be the root of each substructure nodes into the stack, and then access the left child, pop-up stack elements (access to the root node), to access the right child, access to the right child, continue to the root node of each substructure into stack, Then visit the left child… The loop continues until the stack is empty or the pointed root is empty.
three
Subsequent traversal
Again, recursively first
A. Preorder traversal of its left subtree;
B. The right subtree is traversed first;
C. Access the root node.
And then you recurse all the way down, and when you access the node, you can do something about the node, like simply access the value of the node
Below is a binary tree, let’s manually simulate the process of post-order traversal
According to the above process of post-order traversal, the post-order traversal sequence is obtained:
H I D E B F G C A
Copy the codeLet’s implement the logic in code:
class Solution:
def post_order_traverse(self, root) :
if not root:
return
self.post_order_traverse(root.left)
self.post_order_traverse(root.right)
print(root.value, end="")
Copy the codeIt’s still pretty neat, and it’s still rearranging the position of the code statement that accesses the node.
Next comes the non-recursive implementation process
The non-recursive process of the subsequent traversal is more complicated. The subsequent traversal needs to visit the left and right child nodes before accessing the node, which is also the difficulty of non-recursion. It can be done with a helper stack, but it’s not as clear to understand as using two stacks, so today we’re going to use two stacks for non-recursive subsequent traversal.
A. Initialize the root node into s1 b. C. Check whether T has left or right children. If yes, go to b
With the help of the figure, the tree structure is the same, to sort out the idea (long picture, patience, after reading, you will find that the idea is very clear) :
With that thought in mind, it should be clear. Here’s how to write the code:
class Solution:
def post_order_traverse_no_recursion1(self, root) :
s1, s2 = [], []
s1.append(root) # Initialize the root node into S1
while s1:
T = s1.pop() # Pop the top element T in S1 into S2
s2.append(T)
if T.left: # Determine if T has left or right children, if yes, push S1 in turn
s1.append(T.left)
if T.right:
s1.append(T.right)
while s2:
print(s2.pop().value, end="")
Copy the codeIt looks like two stacks are fooling people, in fact, the idea is very clear, the code is easy to achieve!
four
Level traversal
Layer traversal is a BFS category, where each layer is swept along the “tree” hierarchy.
The traversal starts at the root, first enqueues the root, and then starts the loop:
- Join the head node
- Popup the first element, if the first element has left or right children, put them in the queue in turn
- Loop 2 until the queue is empty
Here is a picture to describe the traversal process:
Don’t you think this is very clear? Sometimes I think this kind of long picture is better than the GIF, you can see every step clearly, and there can be a very detailed explanation in the middle. You can give advice on the image display, this aspect can be further.
Let’s start with the code:
class Solution:
def level_order_traverse(self, head) :
if not head:
return
queue = [head]
while len(queue) > 0:
tmp = queue.pop(0)
print(tmp.value, end="")
if tmp.left:
queue.append(tmp.left)
if tmp.right:
queue.append(tmp.right)
Copy the codeThat’s all for today!
The last
1. Deep understanding of recursion, must be more thinking, cough, cough, I have on every morning 10 o ‘clock alarm bell (read the book a hundred times, its meaning from see);
2. The way of thinking guided by the non-recursive traversal of the “tree” is very important;
3. In the next issue of “Basic Traversal”, the list of LeetCode titles and the use of tree recursion will produce some deformation problems related to computing trees
Note: the code will be put on Github later, today you can get the code in the background private message “tree” ha!