Binary tree - preorder traversal (middle left right)

recursion

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        # recursion
        res = []
        def preoder(root):
            if not root: return 
            res.append(root.val)
            preoder(root.left)
            preoder(root.right)
        preoder(root)
        return res

non-recursive

The stack structure is used to assist in the output of results. The stack is characterized by first in and then out, so you need to press in the right and then the left.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:

        # non-recursive 
        res, stack = [], [root]
        while stack:
            node = stack.pop()
            if node:
                res.append(node.val)
                stack.append(node.right)
                stack.append(node.left)
        return res

Binary tree - medium order traversal (left - middle - right)

recursion

First recursively traverse the left subtree, then add the root node, and then traverse the right subtree.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        # recursion
        res = []
        def inorder(root):
            if not root:
                return 
            inorder(root.left)
            res.append(root.val)
            inorder(root.right)
        inorder(root)
        return res

non-recursive

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        # non-recursive 
        res, stack = [], []
        while root or stack:
            if root:
                stack.append(root)
                root = root.left
            else:
                node = stack.pop()
                res.append(node.val)
                root = node.right
        return res

Binary tree - post order traversal (left right middle)

recursion

First traverse the left subtree, then traverse the right subtree, and finally add the root node.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        def postorder(root):
            if not root:
                return 
            postorder(root.left)
            postorder(root.right)
            res.append(root.val)
        postorder(root)
        return res

non-recursive

If the original post order traversal is left right middle, we can construct the structure of middle right left; And because the non recursive stack is used as an auxiliary, we need to switch the left and right, first to the left and then to the right, just like the previous sequence traversal. Finally, flip the list.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        # non-recursive 
        res, stack = [], [root]
        while stack:
            node = stack.pop()
            if node:
                res.append(node.val)
                stack.append(node.left)
                stack.append(node.right)
        return res[::-1]

Binary tree -- sequence traversal

Sequence traversal can also be called width first traversal. First visit the first layer node of the tree, and then visit the second layer node of the tree. In the nodes of the same layer, they are accessed from left to right.

recursion

Recursion needs to write a function or call a function by itself. First, we traverse the root node, and then use the list [layer] Save the node value of the current layer in the form of append. If the node has left and right nodes, take the (left / right) node as the root node to traverse the node value of the layer.

Note: there is a special case. If the current level is equal to the length of the returned list (len(res)), it means that this is a new layer (compared with the previous one), and a list needs to be created in the original list.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        # recursion
        res = []
        def helper(node, level):
            if not node: return []
            if len(res) == level:
                res.append([])
            res[level].append(node.val)
            helper(node.left, level + 1)
            helper(node.right, level + 1)
        helper(root, 0)
        return res

non-recursive

Method 1 is relatively simple, using list generation. for kid in (n.left, n.right) is not very understandable. The initial understanding is: in the nth layer, kid should belong to the left or right of n.

The second method uses queues, which can also be modified to double ended queues. Use collections Deque(), then cur = queue Pop (0) can be changed to cur = queue The purpose of this sentence is to delete the first element. Then, the value of the deleted cur node is put into the temp (temporary list) of the current layer. If the cur node has left and right nodes, it is also put into the queue for traversal.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        # Non recursive (method 1)
        # ans, level = [], [root]
        # while any(level):
        #     ans.append([node.val for node in level])
        #     level = [kid for n in level for kid in (n.left, n.right) if kid]
        # return ans

        # Non recursive (method 2)
        if not root: return []
        res, queue = [], [root]
        while queue:
            temp = []
            for _ in range(len(queue)):
                cur = queue.pop(0)
                temp.append(cur.val)
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
            res.append(temp)
        return res

reference resources: link