# Tree traversal and its basic operations

1. Recursive and iterative realization of binary tree traversal (pre-order, middle-order, post-order, breadth-first traversal)
2. The depth of the binary tree, all paths from the binary tree to the leaf nodes

1. define the binary tree class

```class  TreeNode :
def  __init__ ( self,x ):
self.val=x
= self.left None
self.right = None
duplicated code```
```class  TreeNode  {//Tree
int val;
TreeNode left;
TreeNode right;
TreeNode( int x) {val = x;}
}
Copy code```

The traversal of the binary tree is divided into depth-first traversal (dfs) and breadth-first traversal (bfs). The depth-first traversal is divided into first-order traversal, middle-order traversal, and post-order traversal. bfs is also called hierarchical traversal.

• The iterative implementation of dfs uses stack
• The iterative implementation of bfs uses queue

## Traversal of binary tree

Surrounded area

### Preorder traversal

Traversal order: root node-left child-right child (ABDECF)

Recursive implementation:

```def  preorder ( root ):
if  not root:
return
print (root.val)
preorder(root.left)
preorder(root.right)
Copy code```
```	public  void  preorder (TreeNode root)  {
if (root== null )
return ;
System.out.println(root.val);
this .preorder(root.left);
this .preorder(root.right);
}
Copy code```

Iterative implementation:

```def  preorder ( root ):
stack=[root]
while stack:
s=stack.pop(- 1 )
if s:
print (s.val)
stack.append(s.right)
stack.append(s.left)
Copy code```
```	public  void  preorder (TreeNode root)  {
Deque<TreeNode> st = new LinkedList<> ();
while (!st.isEmpty()) {
TreeNode s=st.pollFirst();
if (s!= null ) {
System.out.println(s.val);
}
}
}
Copy code```

### In-order traversal

Traversal order: left child-root node-right child (DBEACF)

Recursive implementation:

```def  inorder ( root ):
if ( not root):
return
inorder(root.left)
print (root.val)
inorder(root.right)
Copy code```
```	public  void  inorder (TreeNode root)  {
if (root== null ) {
return ;
}
this .inorder(root.left);
System.out.println(root.val);
this .inorder(root.right);
}
Copy code```

Iterative implementation:

```def  inorder ( root ):
stack=[]
while stack or root:
while root: #Down loop until the first leaf node is found
stack.append(root)
root=root.left
root=stack.pop(- 1 )
print (root.val)
root=root.right
Copy code```
```	public  void  inorder (TreeNode root)  {
Deque<TreeNode> st = new LinkedList<> ();
while (!st.isEmpty() || root!= null ) {
while (root!= null ) {
root=root.left;
}
root=st.pollFirst();
System.out.println(root.val);
root=root.right;
}
}
Copy code```

### Post-order traversal

Traversal order: left child-right child-root node (DEBFCA)

Recursive implementation:

```def  postorder ( root ):
if ( not root):
return
postorder(root.left)
postorder(root.right)
Print (root.val)
copying the code```
```	public  void  postorder (TreeNode root)  {
if (root== null )
return ;
this .postorder(root.left);
this .postorder(root.right);
System.out.println(root.val);
}
Copy code```

Iterative implementation:

```def  postorder ( root ):
stack=[]
while stack or root:
while root: #Down loop until the first leaf node is found
stack.append(root)
if root.left: #Left child pushes the stack, if there is no left child, the right child pushes the stack
root=root.left
else :
root=root.right
s=stack.pop(- 1 )
print (s.val) #If the
current node is the left child of the top node of the stack, traverse the right child
if stack and s==stack[- 1 ].left:
root=stack[- 1 ].right
else :
= the root None
duplicated code```

### Level traversal

Traverse order: traverse layer by layer (ABCDEF)

Iterative implementation:

```def  bfs ( root ):
queue=[root]
while queue:
n = len (queue)
for i in  range (n):
q=queue.pop( 0 )
if q:
print (q.val)
queue.append(q.left if q.left else  None )
queue.append (q.right IF q.right the else  None )
copying the code```
```	public  void  bfs (TreeNode root)  {
if (root== null )
return ;
Queue<TreeNode> q = new LinkedList<> ();
q.offer(root);
while (!q.isEmpty()) {
int n=q.size();
while (n> 0 ) {
TreeNode node=q.poll();
System.out.println(node.val);
if (node.left!= null ) {
q.offer(node.left);
}
if (node.right!= null ) {
q.offer(node.right);
}
n--;
}
}
}
Copy code```

## Basic operation

Finding the depth, diameter, and longest path of the same value of the binary tree is actually a process of post-order traversal

### Maximum depth of binary tree

```DEF  maxDepth ( the root ):
IF  Not the root:
return  0
return  . 1 + max (maxDepth (root.left), maxDepth (root.right))
copying the code```
```	public  int  maxDepth (TreeNode root)  {
if (root== null )
return  0 ;
return Math.max( this .maxDepth(root.left), this .maxDepth(root.right))+ 1 ;
}
Copy code```

### Diameter of the tree

Diameter of the tree

```class  Solution  {
int dia= 0 ;
public  int  diameterOfBinaryTree (TreeNode root)  {
depth(root);
return dia;
}
private  int  depth (TreeNode root)  {//Calculate the diameter of each subtree in the process of finding the height of the tree
if (root== null )
return  0 ;
int l=depth(root.left);
int r=depth(root. right);
dia=Math.max(dia, l+r);
return Math.max(l, r)+ 1 ;

}
}
Copy code```

### Longest path of the same value

Longest path of the same value

```class  Solution  {
int res;
public  int  longestUnivaluePath (TreeNode root)  {
maxLen(root);
return res;
}
private  int  maxLen (TreeNode root)  {//Find the longest path with the same value starting from
root if (root== null ) {
return  0 ;
}
int l=maxLen(root.left);
int r=maxLen(root.right);
if (root.left!= null ) {
if (root.left.val==root.val) {
l+= 1 ;
} else {
l = 0 ;
}
}
if (root.right!= null ) {
if (root.right.val==root.val) {
r+= 1 ;
} else {
r = 0 ;
}
}
res=Math.max(res, l+r);
return Math.max(l, r);
}
}
Copy code```

### The maximum path sum in the binary tree

The maximum path sum in the binary tree

```class  Solution  {
int res;
public  int  maxPathSum (TreeNode root)  {
res=root.val; //Pay attention to the initial value of res, the path requires at least one node
maxSum(root);
return res;
}
private  int  maxSum (TreeNode root)  {
if (root== null ) {
return  0 ;
}
int l=maxSum(root.left);
if (l< 0 ){
l = 0 ;
}
int r=maxSum(root.right);
if (r< 0 ){
r = 0 ;
}
res=Math.max(res, l+r+root.val);
return Math.max(l+root.val, r+root.val);
}
}
Copy code```

### The sum of the left leaves

leetcode-cn.com/problems/su...

Recursion: the sum of the left leaves of the tree = the sum of the left leaves of the left subtree + the sum of the left leaves of the right subtree + the value of the current leaf node (if the current node is the left child of the parent node)

The point is to determine whether the current node is the left child of its parent node, so the parameter dir is passed in the recursive function to indicate the left child/right child

```class  Solution  {

public  int  sumOfLeftLeaves (TreeNode root)  {
return leftSum(root, 1 );

}
private  int  leftSum (TreeNode root, int dir)  {//0 represents the left child, 1 is the right child
int sum = 0 ;
if (root== null ) {
return  0 ;
}
if (root.left== null && root.right== null && dir== 0 ) {
return root.val;
}
sum+=leftSum(root.left, 0 );
sum+=leftSum(root.right, 1 );
return sum;

}

}
Copy code```

### Convert binary search tree to accumulative tree

Convert binary search tree to accumulative tree

BST mid-order traversal is in ascending order, and vice versa, descending order, and then accumulate to the current node.

```class  Solution  {
int num= 0 ;
public TreeNode convertBST (TreeNode root)  {
if (root== null )
return  null ;
convertBST(root.right);
root.val+=num;
num=root.val;
convertBST(root.left);
return root;
}

}
Copy code```

### Nearest common ancestor of binary tree

Nearest common ancestor of binary tree

Post-order traversal

```class  Solution :
def  lowestCommonAncestor ( self, root: TreeNode, p: TreeNode, q: TreeNode ) -> TreeNode:
if  not root or root==p or root==q:
return root
left=self.lowestCommonAncestor(root.left,p,q)
right=self.lowestCommonAncestor(root.right,p,q)
if left and right: # p, q are on the opposite side of
root respectively return root
if  not left and  not right: # root's left/right subtree does not contain p, q
return  None
if left: # p, q are not present root of the right subtree
return left
IF right: # the p-, q is not in the root of the left subtree
return right
copy the code```

## Build a binary tree

A binary tree can be constructed according to the preorder and the middle order, and a binary tree can also be constructed according to the postorder and the middle order. Anyway, the middle order can be constructed. Because there is no in-order, the shape of the tree cannot be determined. For example, a tree whose first order is [1,2] and subsequent order [2,1] can have:

```  1
/
2
Copy code```
```    1
/
2
Copy code```

The idea of binary tree problem is mostly recursion, which is to divide the sub-problems, and then recursively build the left subtree and the right subtree.

The last node of the post-order traversal is the root node of the entire tree, so the root node can be determined.

According to the middle sequence, the middle sequence of the left subtree and the middle sequence of the right subtree are obtained.

Regardless of the middle order or the post order, the number of nodes in the left and right subtrees is the same, so the post order sequence of the left subtree and the right subtree can be obtained.

Recursively construct the left and right subtrees.