This is the 7th day of my participation in Gwen Challenge

Recently, I want to sort out my experience of brush algorithm. On the one hand, I want to review and consolidate. On the other hand, I also hope that my sharing can help more friends in learning algorithm.

The column is called “Algorithm Tips”, which will focus on the overall structure of the algorithm, but will not cover all aspects. It is suitable for those who have some algorithm experience to read.

The first part is about binary trees. All the topics and source code of this part have been uploaded to github’s directory. The solution of the problem is implemented in Python and Go.

Tree, binary tree, binary search tree

For a linked list, each node has only one successor node. If there are multiple nodes, it will evolve into a tree; if there are rings between nodes, it will evolve into a directed graph; in particular, if each node has at most two branches and no rings, it will evolve into a binary tree.

For a binary tree, if each node has only one branch, it degenerates into a single linked list.

A binary search tree is a special binary tree in which all elements in the left tree are smaller than the middle node and all elements in the right tree are larger than the middle node.

Traversal of binary trees

Binary tree traversal is a common question in the interview, mainly including pre-order traversal, middle-order traversal, post-order traversal and hierarchical traversal.

  • Front-order traversal: root – left – right
  • Middle order traversal: left – root – right
  • Post-order traversal: left – right – root

Just remember that whether it’s the front, middle, or back, it’s where the root node is traversed.

Next, enter the actual algorithm, I use 144. Binary tree traversal as a demonstration.

Node definition

The first step is to define the nodes of the tree.

Python:

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

Go language description:

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}
Copy the code

Tree traversal can be done recursively and iteratively.

The recursive method

Let’s do it recursively first.

Python language implementation:

class Solution:
    def preorderTraversal(self, root: TreeNode) - >List[int] :
        def preorder(node) :
            if not node: return
            res.append(node.val)
            preorder(node.left)
            preorder(node.right)

        res = []
        preorder(root)
        return res
Copy the code

In the preorder method, the position of the statement can be flexibly adjusted to mid-order traversal or post-order traversal.

Due to the flexibility of the Python language, the above code can also be simplified as:

class Solution:
    def preorderTraversal(self, root: TreeNode) - >List[int] :
        if not root:
            return []
        return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)

Copy the code

Supplementary GO language implementation:

func preorderTraversal(root *TreeNode) (res []int) {
	var preorder func(node *TreeNode)
	preorder = func(node *TreeNode) {
		if node == nil {
			return
		}
		res = append(res, node.Val)
		preorder(node.Left)
		preorder(node.Right)
	}
	preorder(root)
	return
}
Copy the code

The whole idea of recursion is to break down a complex problem into repeating subproblems, and focus only on what logic one node should perform.

Iterative method

The second is iteration, where stack data structures are used.

Python language implementation

class Solution:
    def preorderTraversal(self, root: TreeNode) - >List[int] :
        if not root: return []
        stack, res = [root], []
        while stack:
            tmp = stack.pop()
            res.append(tmp.val)
            if tmp.right:
                stack.append(tmp.right)
            if tmp.left:
                stack.append(tmp.left)
        return res
Copy the code

GO language implementation

func preorderTraversal(root *TreeNode) (res []int) {
	var stack []*TreeNode
	node := root
	fornode ! =nil || len(stack) > 0 {
		fornode ! =nil {
			res = append(res, node.Val)
			stack = append(stack, node)
			node = node.Left
		}
		node = stack[len(stack)- 1].Right
		stack = stack[:len(stack)- 1]}return
}
Copy the code

Iterative method is difficult to think about, need to stack such data structure flexible application, need to read and practice, understand the elements on the stack and off the stack timing.

Sequence traversal

As for the sequence traversal, it is relatively simple, layer by layer to go through.

The example is 102. Sequence traversal of binary trees

Since the paper is too long to write both go and Python solutions, I will use Python to achieve the solution in the future. For other solutions, please refer to my Github.

Python:

from collections import deque

class Solution:
    def levelOrder(self, root: TreeNode) - >List[List[int]] :
        if not root: return []
        res = []
        queue = deque([root])
        while queue:
            tmp = []
            for _ in range(len(queue)):
                node = queue.popleft()
                tmp.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            res.append(tmp)
        return res
Copy the code

The sequential traversal uses the data structure of the queue, which is in Python’s Collections package

Actual combat simulation

By walking through it, I believe you have a general idea of the various tree solutions.

In front, middle and back recursion, it is also called depth first search (DFS).

In sequential traversal, queues are referenced, also known as breadth-first search (BFS).

Next flexible application tree to solve the problem.

I am limited to space here, only to find a sample 111. The minimum depth of binary tree, more questions can see my github.

Python:

class Solution:
    def minDepth(self, root: TreeNode) - >int:
        if not root: return 0
        if not root.left: return self.minDepth(root.right) + 1
        if not root.right: return self.minDepth(root.left) + 1
        return min(self.minDepth(root.left), self.minDepth(root.right)) + 1
Copy the code

This problem is going to give full play to the nature of recursion, and focus on what to do with the characteristic nodes.

Do the boundary condition judgment first, if the node is empty, directly return 0

If the node contains only one child node, return the minimum depth of the node +1

If the node contains left and right nodes, compare the lesser of the two.

There are many similar topics, such as finding the maximum depth of the binary tree, flipping the binary tree, the sum of the paths of the binary tree, etc., are all the same idea.