【LeetCode】94. Middle order traversal of binary tree

---

Their thinking ：

( One )

The middle order of the binary tree is Left root right , First traverse the left half , Then the root node , And the right half .

The left half can be divided according to the initial state , The same is true for the right half , You can use recursion

Take the left node of the root node first and recurse , If the left node is empty, it means to the far left , At this time, this node is the root node of this layer , From left root to right , Add the root node without recursion to the stack , After recursion, the right child node of the root node , If not, return to

---

When implementing recursively , It's the function that calls itself , Nested layer by layer , operating system / Virtual machine automatically helps us use   Stack   To save each called function

Recursion is a tree structure , Literally, it can be understood as repetition “ Recurrence ” and “ Return to ” The process of , When “ Recurrence ” When you reach the bottom, you start “ Return to ”, The process is equivalent to the depth first traversal of the tree .

Call the process ：

dfs(root.left)
	dfs(root.left)
		dfs(root.left)
			 by null return 
		 Print nodes 
		dfs(root.right)
			dfs(root.left)
				dfs(root.left)
				........

Recursive implementation

        res = []    # Store node values 
        def dg(root):
            if not root:        # If the current node is empty , return   , Add node value 
                return
            dg(root.left)   # Follow the left , Join root , Right way traversal 
            res.append(root.val)    
            dg(root.right)
        dg(root)    # Call yourself 
        return res

---

( Two )

Use iteration ： Activities that repeat the feedback process , The result of each iteration will be taken as the initial value of the next iteration .（A Repeated calls to B）

Iteration is a Ring structure , From the beginning , Every iteration goes through the loop , And update the status , Iterations until the end state is reached .

Explain ： Start from the root node to the left node , Every node is stored in the stack , The last entry node is the leftmost node , And then out of the stack , Save its element value , View its right node , Some words , Push , Start from this node to the left node , If there is no right node , Keep going out of the stack , loop , Until all nodes are put into and out of the stack , end

if not root:
            return []
        res = []        # Store node values 
        stack = []      # Save the node temporarily , It's like a stack 
        cur = root      # Set the pointer 
        while cur or stack:     # When cur When the pointing value and stack are empty, there are no elements 
            while cur :     # Add the path from root to left to the stack in turn 
                stack.append(cur)
                cur = cur.left
            node = stack.pop()  # Reach the end , Just take out the value of the last node in the stack and add it to the result res in 
            res.append(node.val)
            cur = node.right     # Looking at the right child node of this node , loop 
        return res      # When all nodes are added to the stack , After the last stack ,res