catalogue
II Traversing binary tree by recursive method
III Iterative (non recursive) traversal of binary trees
(1). Iterative simulation method
(3). Some simple methods of dispersing
I Definition of nodes
Firstly, the definition of nodes is given here. This is how the topics related to leetcode tree define nodes
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}II Traversing binary tree by recursive method
Preorder traversal
Traverse the binary tree, store the preamble sequence of the binary tree in the list, and benchmark leetcode questions 144, 94 and 145
class Solution {
List<Integer> list = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
if(root != null){
list.add(root.val); //Here is the operation on the node
preorderTraversal(root.left);
preorderTraversal(root.right);
}
return list;
}
}
Medium order traversal
class Solution {
List<Integer> list = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
if(root != null){
preorderTraversal(root.left);
list.add(root.val); //Here is the operation on the node
preorderTraversal(root.right);
}
return list;
}
}
Postorder traversal
class Solution {
List<Integer> list = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
if(root != null){
preorderTraversal(root.left);
preorderTraversal(root.right);
list.add(root.val); //Here is the operation on the node
}
return list;
}
}
III Iterative (non recursive) traversal of binary trees
(1). Iterative simulation method
The iterative simulation method of preorder and middle order is relatively simple, which is equivalent to walking the whole binary tree in order. Similar to the following figure, preorder traversal is output when the node is accessed for the first time, and middle order traversal is output when the node is accessed for the second time.
Note that the stack is used here. The node is defined outside, and the root node does not need to push into the stack first, then the loop exit condition, and a node should be added= null, which is different from sequence traversal.
Preorder traversal
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null){
return null;
}
Deque<TreeNode> stack = new LinkedList<>();
TreeNode node = root;
while(!stack.isEmpty() || node != null) {
while (node != null) {
stack.push(node);
list.add(node.val);
node = node.left;
}
node = stack.pop();
node = node.right; //In this step, the stack is empty, but the node is not empty
}
return list;
}
}Medium order traversal
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null){
return list;
}
Deque<TreeNode> stack = new LinkedList<>();
TreeNode node = root;
while(!stack.isEmpty() || node != null){
while (node != null){
stack.push(node);
node = node.left;
}
node = stack.pop();
list.add(node.val);
node = node.right;
}
return list;
}
}Postorder traversal
Post order traversal is a little more complex than pre order and middle order. When a node pop comes out, it is necessary to judge which side it traverses from at that time.
If the right subtree is empty or the right subtree has been traversed before, it comes up from the right. Saving the current node as prev means that the traversal has been completed, and then empty the current node to terminate the traversal of the current node.
If the right subtree is not empty and has not been traversed, it comes up from the left and goes to the right. Here, the current node must be push ed in again, because the current node will be accessed again later.
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root == null) {
return res;
}
Deque<TreeNode> stack = new LinkedList<>();
TreeNode node = root;
TreeNode prev = null;
while (node != null || !stack.isEmpty()) {
while (node != null) {
stack.push(node);
node = node.left;
}
node = stack.pop();
if (node.right == null || node.right == prev) {
//If the right subtree is empty or the right subtree has been traversed before, it comes up from the right. Saving the current node as prev means that the traversal has been completed
//Then empty the current node and terminate the traversal of the current node
res.add(node.val);
prev = node;
node = null;
} else { //If the right subtree is not empty and has not been traversed, it comes up from the left and goes to the right
stack.push(node); //Here, the current node must be push ed in again, because the current node will be accessed again later
node = node.right;
}
}
return res;
}
}(2). Null pointer notation
This null pointer marking method is more general and simple. Simply put, it is to mark with a null pointer so that you can access a node many times, and then do some operations when accessing the node the second time.
Note:
- Stack is used here, not queue. Therefore, when entering the stack, you should first enter the right subtree and then the left subtree. So it simulates the execution of the stack.
- peek is used to get the node. First judge whether the node is null or not. You can't pop it out directly. If it is a null node, it means that you need to pop out the current node. Pop out the empty node first, then get the element, and finally pop.
- Note that this is a stack, first in and then out. If it is a preamble, first enter the right subtree, then the left subtree, and finally the root node. In this way, when it comes out of the stack, it is about the root, that is, the corresponding preamble sequence.
Preorder traversal
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<>();
Stack<TreeNode> st = new Stack<>();
if (root != null) st.push(root);
while (!st.empty()) {
TreeNode node = st.peek();
if (node != null) {
st.pop(); // Pop up the node to avoid repeated operations. Next, add the right, middle and left nodes to the stack
if (node.right!=null) st.push(node.right); // Add the right node (empty nodes are not stacked)
if (node.left!=null) st.push(node.left); // Add left node (empty nodes are not stacked)
st.push(node); // Adding nodes
st.push(null); // The node in has been accessed but has not been processed. Add an empty node as a tag.
} else { // Only when an empty node is encountered, the next node is put into the result set
st.pop(); // Pop up empty node
node = st.peek(); // Retrieve the elements in the stack
st.pop();
result.add(node.val); // Add to result set
}
}
return result;
}
}
Medium order traversal
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<>();
Stack<TreeNode> st = new Stack<>();
if (root != null) st.push(root);
while (!st.empty()) {
TreeNode node = st.peek();
if (node != null) {
st.pop(); // Pop up the node to avoid repeated operations. Next, add the right, middle and left nodes to the stack
if (node.right!=null) st.push(node.right); // Add the right node (empty nodes are not stacked)
st.push(node); // Adding nodes
st.push(null); // The node in has been accessed but has not been processed. Add an empty node as a tag.
if (node.left!=null) st.push(node.left); // Add left node (empty nodes are not stacked)
} else { // Only when an empty node is encountered, the next node is put into the result set
st.pop(); // Pop up empty node
node = st.peek(); // Retrieve the elements in the stack
st.pop();
result.add(node.val); // Add to result set
}
}
return result;
}
}
Postorder traversal
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<>();
Stack<TreeNode> st = new Stack<>();
if (root != null) st.push(root);
while (!st.empty()) {
TreeNode node = st.peek();
if (node != null) {
st.pop(); // Pop up the node to avoid repeated operations. Next, add the right, middle and left nodes to the stack
st.push(node); // Adding nodes
st.push(null); // The node in has been accessed but has not been processed. Add an empty node as a tag.
if (node.right!=null) st.push(node.right); // Add the right node (empty nodes are not stacked)
if (node.left!=null) st.push(node.left); // Add left node (empty nodes are not stacked)
} else { // Only when an empty node is encountered, the next node is put into the result set
st.pop(); // Pop up empty node
node = st.peek(); // Retrieve the elements in the stack
st.pop();
result.add(node.val); // Add to result set
}
}
return result;
}
}
(3). Some simple methods of dispersing
Preorder traversal
The marking method of preorder traversal does not need to be so troublesome
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<>();
Stack<TreeNode> st = new Stack<>();
if (root != null) st.push(root);
while (!st.empty()) {
TreeNode node = st.pop();
result.add(node.val);
if (node.right!=null) st.push(node.right); // Add the right node (empty nodes are not stacked)
if (node.left!=null) st.push(node.left); // Add left node (empty nodes are not stacked)
}
return result;
}
}Postorder traversal
You can also use set to mark. When you visit a node for the first time, put the right and left subtrees of the node on the stack, and then operate on the node for the second time.
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root == null) {
return res;
}
Deque<TreeNode> stack = new LinkedList<>();
Set<TreeNode> set = new HashSet<>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode node = stack.peek();
if(!set.contains(node)){
set.add(node);
if (node.right != null){
stack.push(node.right);
}
if (node.left != null){
stack.push(node.left);
}
}else {
res.add(node.val);
stack.pop();
}
}
return res;
}
}