This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details
preface
As an important data structure, binary tree plays a connecting role in algorithm. It is the extension of array and linked list, and also the basis of graph. So learning binary tree related knowledge is very necessary, and in the relevant operation, binary tree traversal is the most frequent, today to see the binary tree traversal method of 4!
Binary tree data structure
The so-called binary tree refers to a tree structure in which each node has at most two branches. Its branches are usually called “left subtree” and “right subtree”, and their order is fixed and cannot be reversed at will. An example of a binary tree is as follows:
class TreeNode{
int val;
/ / the left subtree
TreeNode left;
/ / right subtree
TreeNode right;
}
Copy the codeThe former sequence traversal
Also known as sequential traversal, the root node is visited first, the left subtree is traversed, and the right subtree is traversed again. When traversing the left and right subtrees, the root node is visited first, then the left subtree is traversed, and finally the right subtree is traversed until the binary tree is empty.
Traversal methods are mainly divided into recursive and iterative methods, and their specific implementation is shown as follows.
recursive
public ArrayList<Integer> preOrderReverse(TreeNode root){
ArrayList<Integer> list = new ArrayList<>();
preOrder(root, list);
return list;
}
public void preOrder(TreeNode root, ArrayList<Integer> list){
if(root ! =null){ list.add(root.val); preOrder(root.left, list); preOrder(root.right, list); }}Copy the codeThe iteration
/** * Use stack to iterate, since stack is a kind of first in last out data structure, the output order is middle, left, right *, so we first add the root node to the stack, then add the right subtree, then add the left subtree */
public ArrayList<Integer> preOrderReverse(TreeNode root){
// stack, first in last out
Stack<TreeNode> stack = new Stack<>();
ArrayList<Integer> list = new ArrayList<>();
if(root ! =null) {/ / into the stack
stack.push(root);
while(! stack.empty()){/ / out of the stack
TreeNode node = stack.pop();
list.add(node.val);
// The stack is a first-in, last-out data structure, so the right subtree is entered first, then the left subtree
if(node.right ! =null){
stack.push(node.right);
}
if(node.left ! =null){ stack.push(node.left); }}}return list;
}
Copy the codeIn the sequence traversal
First the left subtree is traversed, then the root node is visited, and finally the right subtree is traversed again. When traversing the left and right subtrees, the left subtree is traversed first, then the root node is visited, and finally the right subtree is traversed until the binary tree is empty.
Traversal methods are mainly divided into recursive and iterative methods, and their specific implementation is shown as follows.
recursive
public ArrayList<Integer> inOrderReverse(TreeNode root){
ArrayList<Integer> list = new ArrayList<>();
inOrder(root, list);
return list;
}
public void inOrder(TreeNode root, ArrayList<Integer> list){
if(root ! =null){ inOrder(root.left, list); list.add(root.val); inOrder(root.right, list); }}Copy the codeThe iteration
/** * prints in left, middle, and right order * so the left subtree is pushed first, then the middle node, and finally the right subtree ** /
public ArrayList<Integer> inOrderReverse(TreeNode root){
ArrayList<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode curr = root;
while(curr ! =null| |! stack.isEmpty()){// The node is not empty until the stack is pressed
while(curr ! =null){
stack.push(curr);
// Consider the left subtree
curr = curr.left;
}
// The node is empty
curr = stack.pop();
// Add the current value
list.add(curr.val);
// Consider the right subtree
curr = curr.right;
}
return list;
}
Copy the codeAfter the sequence traversal
After traversal first traverses the left subtree, then traverses the right subtree, finally visits the root node, traverses the left and right subtree, still traverses the left subtree first, then traverses the right subtree, finally traverses the root node, until the binary tree is empty, returns!
Traversal methods are mainly divided into recursive and iterative methods, and their specific implementation is shown as follows.
recursive
public ArrayList<Integer> postOrderReverse(TreeNode root){
ArrayList<Integer> list = new ArrayList<>();
postOrder(root, list);
return list;
}
public void postOrder(TreeNode root, ArrayList<Integer> list){
if(root ! =null){ postOrder(root.left, list); postOrder(root.right, list); list.add(root.val); }}Copy the codeThe iteration
public ArrayList<Integer> postOrderReverse(TreeNode root){
List<Integer> list = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode current = root;
// It is used to tell whether the previous node has been accessed
TreeNode last = null;
while(current ! =null| |! stack.isEmpty()){// To the far left of the tree
if(current ! =null){
stack.push(current);
current = current.left;
}else{
// See if the most left node has a right subtree
current = stack.peek();
if(current.right ! =null&& current.right ! = last){ current = current.right; stack.push(current);// Right subtree to the left
current = current.left;
}else{
// Access the node and mark it as accessed
current = stack.pop();
list.add(current.val);
last = current;
current = null; }}}return list;
}
Copy the codeLevel traversal
Hierarchical traversal, also known as breadth-first traversal, gives priority to the node closest to the root node and is usually implemented using queues.
Traversal methods are mainly divided into recursive and iterative methods, and their specific implementation is shown as follows.
recursive
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> lists = new ArrayList<List<Integer>>();
if(root ! =null) {// The root node is not null, recursive
dfs(1, root, lists);
}
return lists;
}
// index: number of layers
public void dfs(int index, TreeNode root, List<List<Integer>> lists){
// Add an empty list if the number of sequences in Lists is less than the number of layers
if(lists.size() < index){
lists.add(new ArrayList<Integer>());
}
// Then add the current node to the subsequence of Lists
lists.get(index - 1).add(root.val);
// This completes the root node
+1 = +1 +1 = +1 +1
if(root.left ! =null){
dfs(index + 1, root.left, lists);
}
if(root.right ! =null){
dfs(index + 1, root.right, lists); }}Copy the codeThe iteration
ArrayList<ArrayList<Integer>> levelOrder(TreeNode root){
List<List<Integer>> res = new ArrayList<>();
Queue<TreeNode> queue = new ArrayDeque<>();
if(root ! =null) {
queue.add(root);
}
while(! queue.isEmpty()) {// Get the length of the current queue, which is equal to the number of nodes in the current layer
int n = queue.size();
// Take all the elements of the queue (i.e. the nodes of this layer) and place them in a temporary list
// If the left/right subtree of the node is not empty, it is queued
List<Integer> level = new ArrayList<>();
int i = 0;
while(i < n){
TreeNode node = queue.poll();
level.add(node.val);
if(node.left ! =null) {
queue.add(node.left);
}
if(node.right ! =null) {
queue.add(node.right);
}
i++;
}
// Add the temporary list to the final return result
res.add(level);
}
return res;
}
Copy the codeconclusion
The above is the data structure binary tree traversal 4 kinds, if you have more about the implementation of various traversal, welcome to leave a message!