# Summary of common algorithms of binary tree

2020-11-06 01:18:19

### Node definition

Binary tree nodes include element values and left and right child node references .

Form like ：

### 1、 front 、 in 、 After the sequence traversal

In front of the binary tree 、 in 、 Before in postorder traversal 、 in 、 The root node ;
Before the order ： Output the root node first , And then the left and right nodes .
Middle preface ： First left , Then output the root node , To the right .
In the following order ： First left and right , Then output the root node .

#### 1.1、 The former sequence traversal

##### 1.1.1、 Recursive implementation

If the node is null, Go straight back to ;
Print out the root node first , Then recursion left subtree , Then recurs the right subtree .
Just meet ： First root , And then around .

##### 1.1.2、 Non recursive implementation

Make full use of the idea of stack , First in, then out .
When the node is not empty , Putting nodes on the stack , Iterate the elements in the stack , Pop up top element , Currently the root element , After that, press the right and left child nodes on the stack respectively . In this way, the order of the child nodes is left first and then right .

### 2、BFS And DFS

Breadth first traversal is to read node elements by layer , We need to use the data structure of the queue .

Starting from the root node , Select a branch to read all the elements , We need to use the data structure of the stack .

### 3、 The depth of the binary tree

104. The maximum depth of a binary tree

#### 3.2、 Depth first

maxDepth Compare the length of each branch to update , Finally get the deepest branch length .

Search by layer , Every step into the floor , depth +1.

### 4、 Binary tree image

Traverse by depth or breadth , Swap the left and right subtrees of nodes .

### 5、 Symmetric binary tree

101. Symmetric binary tree
This problem is a variation of binary tree mirror image , If two binary trees are symmetric , be ：

1. Two root nodes have the same value
2. The left subtree of each tree , Are the same as the right subtree of another tree
Recursive implementation ： Iterative implementation ：

### summary

The algorithm of various topics of binary tree will think of recursion in the first consciousness , But when the recursion depth is too large, there will be stack overflow , So iterations will be used to implement accordingly , Accordingly, the data structure of queue or stack is introduced .
It feels like the most important algorithm is DFS And BFS, among DFS Depth first search uses the FIFO feature of the stack , and BFS Breadth first search uses the first in first out feature of the queue .