Hello, everyone, I am a public number: Java Xiaojie to come on, now working in Jingdong, from time to time to share jingdong interview questions and Java related knowledge, today I will share an article about binary tree (suggested collection, easy to consolidate the foundation).
- Leetcode has solved at least eight problems by the end of this article
- Master pre-order, middle-order, post-order traversal of binary tree and two different implementation methods: recursive and non-recursive
- Non-recursive traversal and hierarchical traversal, with detailed diagrams showing how the elements in the queue/stack move, helps to understand how the code works
Introduction to binary trees
A binary tree is an ordered tree whose nodes have a degree of 2 or less. It is the simplest and most important tree.
The recursion of binary tree is defined as: binary tree is an empty tree, or a non-empty tree consisting of a root node and two disjoint left and right subtrees called root respectively. Left and right subtrees are also binary trees
- The logical binary tree hasFive basic forms, as shown in the figure
- An empty binary tree
- A binary tree with only one root
- Only left subtree
- Complete binary tree
- Only the right subtree
Binary tree attributes:
- Node: Contains a data element and information that points to subtree branches.
- Degree of nodes: The number of subtrees a node has is called the degree of a node.
- Leaf node: Also called terminal node, node with no subtree or node with degree zero.
- Branch node: also called non-terminal node, the node whose degree is not zero is called non-terminal node.
- Tree degree: The maximum degree of all nodes in the tree.
- The hierarchy of nodes: starting from the root node, assume that the root node is layer 1, the child node of the root node is layer 2, and so on. If a node is at layer L, its child node is at layer L+1.
- Tree depth: also known as the height of the tree, the maximum level of all nodes in the tree is called the tree depth.
- Ordered tree: A tree is called an ordered tree if its subtrees are ordered in sequence.
- Unordered tree: A tree is called unordered if its subtrees are not in order.
Binary tree traversal
- There are three binary tree traversal methods
- Pre-order traversal (root left and right) : accesses the root, then the left subtree, then the right subtree.
- Middle order traversal (left root right) : first accesses the left subtree, then the root, then the right subtree.
- Subsequent traversal (left and right roots) : first visits the left subtree, then the right subtree, then the root.
For example, a binary tree that looks like this, traversed by three different traversal methods, the output is, respectively
- Preorder traversal: ABDECFG
- Middle order traversal: DBEAFCG
- Subsequent traversal: DEBFGCA
Let’s use code to implement these three traversals
- Note: There are recursive and non-recursive methods for each traversal of the preceding order, middle order and post order
- Pre-order traversal is depth-first traversal (DFS)
- Hierarchical traversal is breadth-first traversal (BFS)
The binary tree traverses recursively
* Preorder traversal (LeetCode 144)
class Solution {
// Declare the list
ArrayList<Integer> list = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
// If the root node is empty, the empty list is returned
if (root == null) {return new ArrayList<>();
}
// The node is not empty. Add the value of the node to the list
list.add(root.val);
// Determine whether the left node of this node is empty. If not, recursively traverse the left subtree
if(root.left ! =null){
preorderTraversal(root.left);
}
// Determine whether the right node of this node is empty, if not, recursively traverse the right subtree
if(root.right ! =null){
preorderTraversal(root.right);
}
// Finally returns the list
returnlist; }}Copy the code- Middle order traversal (LeetCode 94)
class Solution {
// Declare the list
ArrayList<Integer> list = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
// If the root node is empty, the empty list is returned
if (root == null) {return new ArrayList<>();
}
// Determine whether the left node of this node is empty. If not, the left subtree of this node is recursively traversed
if(root.left ! =null){
inorderTraversal(root.left);
}
// The node is not empty. Add the value of the node to the list
list.add(root.val);
// Determine whether the right node of this node is empty, if not, the right subtree of this node will be recursively traversed
if(root.right ! =null){
inorderTraversal(root.right);
}
// Finally returns the list
returnlist; }}Copy the code- Subsequent traversal (LeetCode 145)
class Solution {
// Declare the list
ArrayList<Integer> list = new ArrayList<>();
public List<Integer> postorderTraversal(TreeNode root) {
// If the root node is empty, the empty list is returned
if (root == null) {return new ArrayList<>();
}
// Determine whether the left node of this node is empty. If not, the left subtree of this node is recursively traversed
if(root.left ! =null){
postorderTraversal(root.left);
}
// Determine whether the right node of this node is empty, if not, the right subtree of this node will be recursively traversed
if(root.right ! =null){
postorderTraversal(root.right);
}
// The node is not empty. Add the value of the node to the list
list.add(root.val);
// Finally returns the list
returnlist; }}Copy the codeThe only difference is that list.add(root.val); The position of the code is different. This line of code represents the traversal (access) in the text.
Posterior traversal (left and right roots) is shown in the following figure
A binary tree is non-recursive traversal
- Using the stack (FILO’s first in, last out feature)
- After each piece of code, there is a specific process of the stack and the relationship between the elements in it. It is recommended to calm down and take a look slowly, which helps to understand how the code works
- The former sequence traversal
class Solution {
List list = new ArrayList();
public List<Integer> preorderTraversal(TreeNode root) {
// If the root node is empty, the empty list is returned
if(root==null) {return new ArrayList();
}
// Declare a stack
Stack<TreeNode> stack = new Stack<>();
// push the node onto the stack
stack.push(root);
// If the stack is not empty
while(! stack.empty()){// Pop the node from the stack
TreeNode node = stack.pop();
// Add to the list
list.add(node.val);
// If the right child of this node is not empty
if(node.right! =null) {The right child node is pushed first and then out
stack.push(node.right);
}
// If the left child of this node is not empty
if(node.left! =null) {// Push it to the stack because the stack is first and then out, so the left child node is pushed first}}// Return the list
returnlist; }}Copy the code
- In the sequence traversal
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
// Check whether the node is empty. If so, return the empty list
if (root == null) {return new ArrayList();
}
// Declare the list to store the results
List<Integer> list = new ArrayList();
// Declare a stack
Stack<TreeNode> stack = new Stack<>();
// When the node is not empty or the stack is not empty
while(root ! =null| |! stack.empty()){// When the node is not empty
while(root ! =null) {// Push the node to the stack
stack.push(root);
// Point the node to its left child
root = root.left;
}
// If the stack is not empty
if(! stack.empty()){// Pop the stack element out
TreeNode node = stack.pop();
// Add to the list
list.add(node.val);
// Point the node to its right childroot = node.right; }}returnlist; }}Copy the code
- After the sequence traversal
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
// If the root node is empty, the empty list is returned
if (root == null) {return new ArrayList<>();
}
// Declare the list
ArrayList<Integer> list = new ArrayList<>();
// declare stack A
Stack<TreeNode> stackA = new Stack<TreeNode>();
// declare stack B
Stack<TreeNode> stackB = new Stack<TreeNode>();
// push the secondary element onto A
stackA.push(root);
// stack A is not empty
while(! stackA.empty()){// Get the element pressed in
TreeNode node = stackA.pop();
// push into B
stackB.push(node);
// When the left child of this node is not empty
if(node.left ! =null) {// push A
stackA.push(node.left);
}
// When the right child of this node is not empty
if(node.right ! =null) {// push AstackA.push(node.right); }}// stack B is not empty
while(! stackB.empty()){// Take the element and add it to the list
TreeNode node = stackB.pop();
list.add(node.val);
}
// Finally returns the list
returnlist; }}Copy the code
Binary tree Sequence Traversal (BFS)
- LeetCode 102 order traversal of binary trees
- Use queue (FIFO first-in, first-out feature) code after the queue and the relationship between the elements of the specific process, it is recommended to calm down and slowly look, help to understand how the code operates
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<List<Integer>>();
}
// Declare a list to store each row of data
List<List<Integer>> result = new ArrayList<>();
// Declare a queue
LinkedList<TreeNode> queue = new LinkedList<>();
// If the root node is not empty, enqueue it
queue.offer(root);
// If the queue is not empty, there is data in the queue
while(! queue.isEmpty()) {// Store the data line for each row
List<Integer> line = new ArrayList<Integer>();
// Save the number of existing data in the queue. These are the values to be added to each row list
int size = queue.size();
for (int i=0; i<size; i++){// Fetch queue nodes (FIFO first in first out)
TreeNode node = queue.poll();
line.add(node.val);
if(node.left ! =null) {
queue.offer(node.left);
}
if(node.right ! =null) {
queue.offer(node.right);
}
}
result.add(line);
}
returnresult; }}Copy the code
Leetcode binary tree exercises
- So here we have an understanding of pre-order (DFS), mid-order, post-order, recursive/non-recursive, and hierarchical traversal (BFS) of binary trees (if all the above diagrams are digested)
Then let’s try some leetcode problems while the iron is hot! (There are only minor changes to the overall code, because the general idea is the same, it is easy to digest the above content)
- Leetcode-257 all paths to the binary tree
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
if (root == null) {return new ArrayList<>();
}
ArrayList<String> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<TreeNode>();
// This stack stores the path, the same operation as the stack of the previous storage node
Stack<String> path = new Stack<String>();
stack.push(root);
path.push(root.val+"");
while(! stack.empty()){ TreeNode node = stack.pop(); String p = path.pop();// When the stack is a leaf node, the path in the stack is a complete path, which can be added to the result
if (node.right == null && node.left == null ){
list.add(p);
}
// If the right child node is not empty
if(node.right ! =null){
stack.push(node.right);
// Continue pushing the temporary path
path.push(p+"- >"+node.right.val);
}
// If the left child is not empty
if(node.left ! =null){
stack.push(node.left);
// Continue pushing the temporary path
path.push(p+"- >"+node.left.val); }}returnlist; }}Copy the code- The maximum depth of the leetcode-104 binary tree is the same as the finger offer 55-I
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {return 0;
}
LinkedList<TreeNode> queue = new LinkedList<>();
int result = 0;
queue.offer(root);
while(! queue.isEmpty()){/ / the layer number of + 1
result++;
// This is the number of nodes in the current layer
int size = queue.size();
for (int i=0; i<size; i++){// You can count again only after you have cleared the queue
TreeNode node = queue.poll();
if(node.left ! =null) {// If the outgoing node has left children, the node is in the queue
queue.offer(node.left);
}
if(node.right ! =null) {// If the outgoing node has a right child node, it joins the queuequeue.offer(node.right); }}}// Return the number of layers
returnresult; }}Copy the code- Order traversal of leetcode-107 binary tree 2
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
if (root == null) {return new ArrayList<List<Integer>>() ;
}
List<List<Integer>> result = new ArrayList<List<Integer>>() ;
LinkedList<TreeNode> queue = new LinkedList<>();
// Declare a stack to store nodes at each level
Stack<ArrayList<Integer> > stack = new Stack<>();
queue.offer(root);
while(! queue.isEmpty()){int size = queue.size();
ArrayList<Integer> list = new ArrayList<>();
for (int i=0; i<size; i++){ TreeNode node = queue.poll(); list.add(node.val);if(node.left ! =null){
queue.offer(node.left);
}
if(node.right ! =null){ queue.offer(node.right); }}// Push the nodes of this layer onto the stack
stack.push(list);
}
// If the stack is not empty, popup the result, thus traversing the binary tree from the bottom up
while(! stack.isEmpty()){ ArrayList<Integer> list = stack.pop(); result.add(list); }returnresult; }}Copy the codeconclusion
With this article, we can solve at least the following problems in Leetcode
-
Preorder traversal (LeetCode 144)
-
Middle order traversal (LeetCode 94)
-
Subsequent traversal (LeetCode 145)
-
LeetCode 102 order traversal of binary trees
-
Leetcode-257 all paths to the binary tree
-
The maximum depth of the leetcode-104 binary tree is the same as the finger offer 55-I
-
Order traversal of leetcode-107 binary tree 2
Past wonderful recommendation
- The interviewer of JINGdong asked me: “Talk about MySql affairs,MVCC? (Good article, suggested collection)”
- Hello, my name is AQS (Series 1: Locking)
- Do you know the interview question?
- ? Thread pools can be reused.
- Volatile. You changed your mind. I saw it
Pour out
If you think this article has a little help for yourself, welcome to pay attention to this public account Java xiaojie to refueling
- You are very welcome to the number of main readers to exchange and learn together, open white forwarding each other, the network lead, cherish this section of fate
If this article is wrong, please point it out. See you in the next article, ladies and boys. Follow me and start our story