Recursive and non-recursive traversal of binary tree before, middle and after

The former sequence traversal

Leetcode – The prior traversal of a binary tree

Given a binary tree, return its prior traversal. Example:

Input: [1, NULL,2,3] 1\2/3 Output: [1,2,3]Copy the code

Simple recursive

1. The former sequence traversal

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
    def preorderTraversal(self, root: TreeNode) - >List[int] :
        result = []
        def visit(node) :
            if not node:
                return 
            # ==== Before, middle, and after are distinguished only in the order of the three lines ====
            result.append(node.val)
            visit(node.left)
            visit(node.right)
            # = = = = = = = = =
        visit(root)
        return result
Copy the code

2. Middle-order, post-order traversal only changes the append order of the visit function without pasting code.

Non-recursive thinking

1. The root node is pushed
2. Take the top node and put it in the result List, pushing the right and left children of the node onto the stack.
3. Repeat step 2 until the stack is empty, returning the resulting List

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
    def preorderTraversal(self, root: TreeNode) - >List[int] :
        result = []
        if root is None:
            return result
        stack = []
        node = root
        stack.append(node)
        while len(stack) > 0:
            node = stack.pop()
            result.append(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return result
Copy the code

In the sequence traversal

Leetcode – Middle order traversal of binary trees

Given a binary tree, return its middle-order traversal. Example:

Input: [1, NULL,2,3] 1\2/3 Output: [1,3,2]Copy the code

Non-recursive thinking

1. For any node, we put it on the stack, and then we access its left child, which we can think of as a node, and then we continue to access its left child, until we reach a node whose left child is empty.
2. Get the node from the top of the stack and place it in the result List. If the node has a right node, do step 1 for its right subtree.
3. Until the stack is empty, the traversal is complete, and the result List is returned.

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
    def inorderTraversal(self, root: 'TreeNode') - > 'List[int] ':
        stack = []
        result = []
        node = root
        while (node is not None) or (len(stack) ! =0) :while node is not None:
                stack.append(node)
                node = node.left
            if len(stack) ! =0:
                node = stack.pop()
                result.append(node.val)
                node = node.right
        return result
Copy the code

After the sequence traversal

Leetcode – Backorder traversal of a binary tree

Given a binary tree, return its backward traversal. Example:

Input: [1, NULL,2,3] 1\2/3 Output: [3,2,1]Copy the code

Thinking a

Start traversing the left child of the node, and record the status of each node as it is pushed. 1 indicates that there is a right node, 0 indicates that there is no right node. Check the state of the node before exiting the stack. 0 is exiting the stack. 1 traverses the right node of the node and sets its state to 0.

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
    def postorderTraversal(self, root: TreeNode) - >List[int] :
        result = []
        stack = []
        node = root
        while node is not None or len(stack) > 0:
            while node is not None:
                if node.right:
                    stack.append([node, 1])
                else:
                    stack.append([node, 0])
                node = node.left
                
            if len(stack) > 0:
                stack_node = stack[-1]
                if stack_node[1] = =1:
                    node = stack_node[0].right
                    stack[-1] [1] = 0
                else:
                    result.append(stack_node[0].val)
                    stack.pop()
        return result
Copy the code

Idea 2

If it is a child node of the current node, it indicates that both the left and right nodes have been accessed. The current node is removed from the stack and the object recorded by Pre is updated.

class Solution:
    def postorderTraversal(self, root: TreeNode) - >List[int] :
        result = []
        stack = []
        node = root
        pop_node = None
        while node is not None or len(stack) > 0:
            while node is not None:
                stack.append(node)
                node = node.left
                
            if len(stack) > 0:
                stack_node = stack[-1]
                if stack_node.right:
                    if pop_node is stack_node.right:
                        result.append(stack_node.val)
                        pop_node = stack.pop()
                    else:
                        node = stack_node.right
                else:
                    result.append(stack_node.val)
                    pop_node = stack.pop()
        return result
Copy the code

Thought three

A trick. The order of access is not post-traversal. Instead, the order of pre-traversal is changed to “root right-left”, and the result List is reversed (or the results of the traversal are pushed onto the result List), resulting in the order of “left-right root”.

class Solution:
    def postorderTraversal(self, root: TreeNode) - >List[int] :
        result = []
        stack = []
        if root is None:
            return result
        stack.append(root)
        while len(stack)>0:
            node = stack.pop()
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
            result.insert(0, node.val)
        return result
Copy the code