Small knowledge, big challenge! This paper is participating in theEssentials for programmers”Creative activities

## Implement binary tree preorder, middle order and post order traversal

Problem description

Given a binary tree, print all nodes in the first, middle, and last order of the binary tree.

Requirements: Space complexity is O(n), time complexity is O(n).

Example:

Input: 1 \ [1, null, 2, 3] two-thirds of output: [[1, 2, 3], 31 [1], [3, 2, 1]]Copy the code

To analyze problems

When we get this problem, first we need to know what pre-ordered traversal, mid-ordered traversal and post-ordered traversal are.

  1. Sequential traversal: The tree is traversed in the order of root node -> left subtree -> right subtree. The left and right subtrees are traversed in the same order until the entire tree is traversed.

  2. Middle-order traversal: Traversal the tree in the order of left subtree -> root node -> right subtree. Traversal the left and right subtrees in the same order until the whole tree is traversed.

  3. Subsequent traversal: Traversal the tree in the order of left subtree -> right subtree -> root, and traversal the left and right subtrees in the same order until the entire tree is traversed.

According to the definition of pre-order, middle-order and post-order of binary tree, we can intuitively think of recursively traversing the whole tree. Let’s take a look at how to implement the first, middle, and last traversal of a binary tree recursively.

recursive

Using recursive traversal, when the left or right subtree of the root node is not empty, we treat the left or right subtree as if it were a complete tree. Let’s look at the implementation of the code.

And just to make it easier to understand, let’s look at the definition of a node.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
Copy the code

The first sequence traversal

    def preorder(self,root):
        if not root:
            return
        self.res.append(root.val)
        self.preorder(root.left)
        self.preorder(root.right)
Copy the code

In the sequence traversal

    def inorder(self,root):
        if not root:
            return
        self.inorder(root.left)
        self.res.append(root.val)
        self.inorder(root.right)
Copy the code

Subsequent traversal

    def postorder(self, root):
        if not root:
            return
        self.postorder(root.left)
        self.postorder(root.right)
        self.res.append(root.val)
Copy the code

The complete implementation of the code

class Solution:
    res=[]
    def threeOrders(self, root):
        result = []
        self.preorder(root)
        result.append(self.res[:])
        self.res.clear()
        self.inorder(root)
        result.append(self.res[:])
        self.res.clear()
        self.postorder(root)
        result.append(self.res[:])
        self.res.clear()
        return result
        
    def postorder(self, root):
        if not root:
            return
        self.postorder(root.left)
        self.postorder(root.right)
        self.res.append(root.val)

    def preorder(self,root):
        if not root:
            return
        self.res.append(root.val)
        self.preorder(root.left)
        self.preorder(root.right)

    def inorder(self,root):
        if not root:
            return
        self.inorder(root.left)
        self.res.append(root.val)
        self.inorder(root.right)
Copy the code